动态数组是如何工作和实现的？
本文概述
动态数组" title="动态数组">动态数组(C ++中的向量, Java中的ArrayList)会在我们尝试插入时自动增长, 而新项目没有更多空间了。通常, 该区域的大小会增加一倍。
可以通过分配固定大小的数组(通常大于立即需要的元素数量)来构造简单的动态数组。动态数组的元素连续存储在基础数组的开始处, 而到基础数组末尾的其余位置则保留或未使用。通过使用保留空间, 可以在恒定时间内将元素添加到动态数组的末尾, 直到该空间被完全消耗为止。
当所有空间都被消耗掉并且要添加一个附加元素时, 需要增加基础固定大小的数组的大小。通常, 调整大小是很昂贵的, 因为你必须分配一个更大的数组, 并从该数组中复制所有你已过度使用的元素, 然后才能最终添加项目。
方法：当我们在数组中输入一个元素但数组已满时, 你将创建一个函数, 该函数将创建一个新数组, 其大小为double值, 或者根据你的需要, 将所有元素从先前数组复制到新数组中, 并返回此新数组。另外, 我们可以减小数组的大小。并在给定位置添加元素, 然后在默认位置和该位置移除该元素。
动态阵列的主要功能
添加元素：如果数组大小不足, 请在末尾添加元素, 然后扩展数组的大小, 并在原始数组和给定索引的末尾添加元素。完成所有复制操作需要O(n)时间, 其中n是数组中元素的数量。附加费用很高。在固定长度的数组中, 追加仅花费O(1)时间。
但是, 只有在我们插入完整数组时, 追加操作才会占用O(n)时间。这是非常罕见的, 特别是如果每次空间用完时我们将数组的大小加倍。因此, 在大多数情况下, 附加时间仍为O(1)时间, 有时为O(n)时间。
在动态数组中, 可以在需要时创建固定大小的数组, 并在数组中添加更多元素, 然后使用以下方法：
删除元素：从数组中删除元素, 默认为remove()方法, 从末尾删除元素, 仅在最后一个索引处存储零, 还可以通过调用i为索引的removeAt(i)方法在特定索引处删除元素。 removeAt(i)方法将所有右元素从给定索引移到左侧。
调整数组大小：当数组右侧的数据为空/零(不包括由你添加)时, 该数组将占用未返回的内存, 则srinkSize()方法将释放额外的内存。当所有空间都被消耗掉并且要添加一个附加元素时, 则基础固定大小的数组需要增加大小。通常, 调整大小是很昂贵的, 因为你必须分配一个更大的数组, 并从该数组中复制所有你已过度使用的元素, 然后才能最终添加项目。
动态数组的简单代码。在下面的代码中, 数组将变为完整大小, 我们将所有元素复制到新的double大小数组(可变大小数组)中。示例代码如下
Java
// Java program deals with all operation of a dynamic array// add, remove, resize memory of array is the main feature
public class DynamicArray {
// create three variable array[] is a array, // count will deal with no of element add by you and
// size will with size of array[]
private int array[];
private int count;
private int size;
// constructor initialize value to variable
public DynamicArray()
{
array = new int [ 1 ];
count = 0 ;
size = 1 ;
}
// function add an element at the end of array
public void add( int data)
{
// check no of element is equql to size of array
if (count == size) {
growSize(); // make array size double
} // insert element at end of array
array[count] = data;
count++;
}
// function makes size double of array
public void growSize()
{
int temp[] = null ;
if (count == size) {
// temp is a double size array of array
// and store array elements
temp = new int [size * 2 ];
{
for ( int i = 0 ; i < size; i++) {
// copy all array value into temp
temp[i] = array[i];
}
}
}
// double size array temp initialize
// into variable array again
array = temp;
// and make size is double also of array
size = size * 2 ;
}
// function shrink size of array
// which block unnecessary remove them
public void shrinkSize()
{
int temp[] = null ;
if (count > 0 ) {
// temp is a count size array
// and store array elements
temp = new int [count];
for ( int i = 0 ; i < count; i++) {
// copy all array value into temp
temp[i] = array[i];
}
size = count;
// count size array temp initialize
// into variable array again
array = temp;
}
}
// function add an element at given index
public void addAt( int index, int data)
{
// if size is not enough make size double
if (count == size) {
growSize();
}
for ( int i = count - 1 ; i >= index; i--) {
// shift all element right
// from given index
array[i + 1 ] = array[i];
}
// insert data at given index
array[index] = data;
count++;
}
// function remove last element or put
// zero at last index
public void remove()
{
if (count > 0 ) {
array[count - 1 ] = 0 ;
count--;
}
}
// function shift all element of right
// side from given index in left
public void removeAt( int index)
{
if (count > 0 ) {
for ( int i = index; i < count - 1 ; i++) {
// shift all element of right
// side from given index in left
array[i] = array[i + 1 ];
}
array[count - 1 ] = 0 ;
count--;
}
}
public static void main(String[] args)
{
DynamicArray da = new DynamicArray();
// add 9 elements in array
da.add( 1 );
da.add( 2 );
da.add( 3 );
da.add( 4 );
da.add( 5 );
da.add( 6 );
da.add( 7 );
da.add( 8 );
da.add( 9 );
// print all array elements after add 9 elements
System.out.println( "Elements of array:" );
for ( int i = 0 ; i < da.size; i++) {
System.out.print(da.array[i] + " " );
}
System.out.println();
// print size of array and no of element
System.out.println( "Size of array: " + da.size);
System.out.println( "No of elements in array: " +
da.count);
// shrinkSize of array
da.shrinkSize();
// print all array elements
System.out.println( "Elements of array " +
"after shrinkSize of array:" );
for ( int i = 0 ; i < da.size; i++) {
System.out.print(da.array[i] + " " );
}
System.out.println();
// print size of array and no of element
System.out.println( "Size of array: " + da.size);
System.out.println( "No of elements in array: " +
da.count);
// add an element at index 1
da.addAt( 1 , 22 );
// print Elements of array after adding an
// element at index 1
System.out.println( "Elements of array after" +
" add an element at index 1:" );
for ( int i = 0 ; i < da.size; i++) {
System.out.print(da.array[i] + " " );
}
System.out.println();
// print size of array and no of element
System.out.println( "Size of array: " + da.size);
System.out.println( "No of elements in array: " +
da.count);
// delete last element
da.remove();
// print Elements of array after delete last
// element
System.out.println( "Elements of array after" +
" delete last element:" );
for ( int i = 0 ; i < da.size; i++) {
System.out.print(da.array[i] + " " );
}
System.out.println();
// print size of array and no of element
System.out.println( "Size of array: " + da.size);
System.out.println( "No of elements in array: " +
da.count);
// delete element at index 1
da.removeAt( 1 );
// print Elements of array after delete
// an element index 1
System.out.println( "Elements of array after" +
" delete element at index 1:" );
for ( int i = 0 ; i < da.size; i++) {
System.out.print(da.array[i] + " " );
}
System.out.println();
// print size of array and no of element
System.out.println( "Size of array: " + da.size);
System.out.println( "No of elements in array: " +
da.count);
}
}
C#
// C# program deals with all operation // of dynamic array add, remove, resize
// memory of array is the main feature
using System;
public class DynamicArray
{
// create three variable array[] is
// a array, count will deal with no
// of element add by you and
// size will with size of array[]
private int []array;
private int count;
private int size;
// constructor initialize value to variable
public DynamicArray()
{
array = new int [1];
count = 0;
size = 1;
}
// function add an element at the end of array
public void add( int data)
{
// check no of element is equql to size of array
if (count == size)
{
growSize(); // make array size double
}
// insert element at end of array
array[count] = data;
count++;
}
// function makes size double of array
public void growSize()
{
int []temp = null ;
if (count == size)
{
// temp is a double size array of array
// and store array elements
temp = new int [size * 2];
{
for ( int i = 0; i < size; i++)
{
// copy all array value into temp
temp[i] = array[i];
}
}
}
// double size array temp initialize
// into variable array again
array = temp;
// and make size is double also of array
size = size * 2;
}
// function shrink size of array
// which block unnecessary remove them
public void shrinkSize()
{
int []temp = null ;
if (count > 0)
{
// temp is a count size array
// and store array elements
temp = new int [count];
for ( int i = 0; i < count; i++)
{
// copy all array value into temp
temp[i] = array[i];
}
size = count;
// count size array temp initialize
// into variable array again
array = temp;
}
}
// function add an element at given index
public void addAt( int index, int data)
{
// if size is not enough make size double
if (count == size)
{
growSize();
}
for ( int i = count - 1; i >= index; i--)
{
// shift all element right
// from given index
array[i + 1] = array[i];
}
// insert data at given index
array[index] = data;
count++;
}
// function remove last element or put
// zero at last index
public void remove()
{
if (count > 0)
{
array[count - 1] = 0;
count--;
}
}
// function shift all element of right
// side from given index in left
public void removeAt( int index)
{
if (count > 0)
{
for ( int i = index; i < count - 1; i++)
{
// shift all element of right
// side from given index in left
array[i] = array[i + 1];
}
array[count - 1] = 0;
count--;
}
}
// Driver code
public static void Main()
{
DynamicArray da = new DynamicArray();
// add 9 elements in array
da.add(1);
da.add(2);
da.add(3);
da.add(4);
da.add(5);
da.add(6);
da.add(7);
da.add(8);
da.add(9);
// print all array elements after add 9 elements
Console.WriteLine( "Elements of array:" );
for ( int i = 0; i < da.size; i++)
{
Console.Write(da.array[i] + " " );
}
Console.WriteLine();
// print size of array and no of element
Console.WriteLine( "Size of array: " + da.size);
Console.WriteLine( "No of elements in array: " +
da.count);
// shrinkSize of array
da.shrinkSize();
// print all array elements
Console.WriteLine( "Elements of array " +
"after shrinkSize of array:" );
for ( int i = 0; i < da.size; i++)
{
Console.Write(da.array[i] + " " );
}
Console.WriteLine();
// print size of array and no of element
Console.WriteLine( "Size of array: " + da.size);
Console.WriteLine( "No of elements in array: " +
da.count);
// add an element at index 1
da.addAt(1, 22);
// print Elements of array after adding an
// element at index 1
Console.WriteLine( "Elements of array after" +
" add an element at index 1:" );
for ( int i = 0; i < da.size; i++)
{
Console.Write(da.array[i] + " " );
}
Console.WriteLine();
// print size of array and no of element
Console.WriteLine( "Size of array: " + da.size);
Console.WriteLine( "No of elements in array: " +
da.count);
// delete last element
da.remove();
// print Elements of array after delete last
// element
Console.WriteLine( "Elements of array after" +
" delete last element:" );
for ( int i = 0; i < da.size; i++)
{
Console.Write(da.array[i] + " " );
}
Console.WriteLine();
// print size of array and no of element
Console.WriteLine( "Size of array: " + da.size);
Console.WriteLine( "No of elements in array: " +
da.count);
// delete element at index 1
da.removeAt(1);
// print Elements of array after delete
// an element index 1
Console.WriteLine( "Elements of array after" +
" delete element at index 1:" );
for ( int i = 0; i < da.size; i++)
{
Console.Write(da.array[i] + " " );
}
Console.WriteLine();
// print size of array and no of element
Console.WriteLine( "Size of array: " + da.size);
Console.WriteLine( "No of elements in array: " +
da.count);
}
}
/* This code contributed by PrinciRaj1992 */
输出如下：
Elements of array:1 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0
Size of array: 16
No of elements in array: 9
Elements of array after shrinkSize of array:
1 2 3 4 5 6 7 8 9
Size of array: 9
No of elements in array: 9
Elements of array after add an element at index 1:
1 22 2 3 4 5 6 7 8 9 0 0 0 0 0 0 0 0
Size of array: 18
No of elements in array: 10
Elements of array after delete last element:
1 22 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0
Size of array: 18
No of elements in array: 9
Elements of array after delete element at index 1:
1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0
Size of array: 18
No of elements in array: 8
以上是 动态数组是如何工作和实现的？ 的全部内容， 来源链接： utcz.com/p/202570.html
