Dynamic Array

Dynamic Array is the extended version of normal array , which is growable or resizable.it is an random access type array.We can implement it by fixed size ,and if more memory is required then create the new array and double the size of this array and copy all the elements from the original array ,as well as delete original array.Similarly remove the array size by half if count of elements are less than half.
means as per our requirements we can grow array size and also reduce the size of array.
When we are growing array size then this process is something expensive but amortized performance/cost is good but as not as much good.

Approach to implements the Dynamic Array

There is tow situations ,first when we need to grow the size of array and second when we have to reduce the array size,

• 1-Grow Array Size :Suppose array has been fulfilled and still we want to add the elements into the array.
  Example :

We want to add(say element 70) more elements into Arr.then we have to calculate the size(say m) of the Arr and create one new Array ArrNew of size 2*m. and copy all the element from Arr to ArrNew.

Now ArrNew has been created and copied all the elements from the original array, So we have to delete Original Array(Arr).

• 2-Reduce Array Size : Let us consider that after one element deletion ,less than half of the array size is used and more memory block is not used then we have to delete half of array size.
  Example :

So this was an example of Dynamic array implementation.

Code Implementation of Dynamic Array

                            /*Size Growing Implementation*/
#include <stdio.h>

int main()
{
    int Arr[] = {20,40,10,90};             //Original Array
    int SIZE =sizeof(Arr)/sizeof(Arr[0]);  // Length of Original Array
    
    printf("Insert the Element 200 at the end....\nBut Array is full ,So create a new Array..\n");
    int ArrNew[2*SIZE];   //New Array Declaration of 2*SIZE
    
    for(int i=0;i<2*SIZE;i++)
    {
        if(i<SIZE)
        {
         ArrNew[i]=Arr[i];    // Copying the elements from Original Array to ArrNew
        }
        else
        {
            ArrNew[i]=0;     // Empty Block is filled by 0
        }
    }
    
    ArrNew[SIZE]=200;       // inserting the new element 200
    
    printf("Array After Insertion....\n");
    for(int i=0;i<2*SIZE;i++)  // Print the ArrNew after insertion
    {
        printf("%d ",ArrNew[i]);
    }
    return 0;
}

Complexity Comparison

• Following table is for Complexity Comparison between 1-D Array and Dynamic Array :

Parameter	1-D Array	Dynamic Array
Indexing	O(1)	O(1)
Insertion at beginning	O(n),if array is not completely full(for relocation/shifting of the elements)	O(n)
Deletion at beginning	O(n),if array is not completely full(for relocation of the elements)	O(n)
Insertion at ending	O(1) , if array is not completely full	O(1),when array is not full. O(n),when array is full.
Deletion at ending	O(1)	O(n)
Middle Insertion	O(n),when array is not full(For relocation/shifting of the elements)	O(n)
Middle Deletion	O(n),when array is not full(For relocation/shifting of the elements)	O(n)

Advantages of Dynamic Array

• Dynamic Array has good Locality of reference.
• Good data cache utilization.
• Low memory uses
• faster indexing and iteration due to good Locality of reference.
• Random Accessing.

Applications of Dynamic Array

• Python List data type is an Dynamic array implementation.
• Hashed array tree algorithm is implemented by Dynamic Array.
• ArrayList of Java is a type of Dynamic Array.
• C++ vector is implemented by Dynamic Array.