Introduction

An array is a container which can store a fixed number of elements of a same data type. As the size is static in nature arrays are also known as static arrays. In arrays the size of the array must be given during declaration of the array itself. What if we want to add more elements but there is no space left? This is where dynamic arrays comes into the existence.

What is dynamic array ?

Dynamic array (also known as resizable array, growable array, dynamic table, or array list) is a random access variable-size data structure to store collection of data. A dynamic array is a contiguous area of memory whose size changes dynamically when required. In dynamic arrays the size of the arrays varies over time. In dynamic arrays, when there is no space left to add more elements the array size grows automatically and the array shrinks if there is lot of unused space left in the array due to frequent removal operations.

Most of the programming languages already have the implementation for dynamic arrays. ArrayList in java, vector in c++, list in python.

Working of a dynamic array

Whenever we insert an element in the array, if the array is not full, we insert the element otherwise we create a new array whose size is double the size of the original array and copy all the elements of original array into the newly created array and then we continue the newly created array as actual array by free up the memory occupied by the original array.

For example we have an array of size 5 and we have already stored 4 values in it

1int[] array = new int[5] 
2array[0] = 10 
3array[1] = 20 
4array[2] = 30 
5array[3] = 40 

Now if we want to insert a new value, as the array size is not full, we can insert new value at index 4 which is our 5 element of the array.

1array[4] = 50 

Now we want to insert one more value , as the array size is full, we need to perform the following operations

• Create new array whose size is double of actual array or original array
• Copy the elements from original array to newly created array
• Free up original array and consider the newly created array as actual array or original array going forward.

1Step1 : create new array with double the size 
2        example : int[] newArray = new int[10] // 2*5 (double the original size) 
3 
4Step2: copy all values of array into new array 
5        for i : 0 to 4 newArray[i] = array[i] 
6 
7Step3: Now update array to newArray  
8       array = newArray  

Initialization

The initialization of dynamic array is same as static array. It first created as an array of fixed size. As in dynamic arrays the size varies over time, the actual size which is allocated in memory is knows as capacity and the number of elements which are actually present in the array is known as size.

Operations :

Below are the parameters which are used to define algorithm of dynamic array operations.

• array – name of the dynamic array

• capacity – size of the the dynamically allocated array. i.e., the number of elements that the array can hold

• size – number of elements currently present in the array.

  

Resize Operation

Resize operation is used in following two scenarios:

• When the array is full and we need to insert more elements – In this case array needs to grow to incorporate further insert operations.
• When there is large amounts of unused space in the array- In this case array needs to shrink to free up the unused space.

1 void resize(int newCapacity) : 
2 
3     capacity = newCapacity 
4
5     // newCapacity is decided based on grow (during add) 
6     // or shrink (during delete) operation 
7     int[] newArray = new int[newCapacity] 
8 
9     for i-> 0 to size-1 
10        // copy elements from the original array to newly created array
11        newArray[i] = array[i]   
12 
13        // Newly created array will be considered as the original array 
14        array = newArray      

Add / Insert

1  void add(int ele) : 
2    // If the array is full 
3    if size == capacity 
4        resize(2*capacity)  
5
6    // insert element     
7    array[size] = ele 
8
9    // increment size
10    size = size + 1  

The below diagram shows how array grows dynamically.

To understand this, Initially create an array of fixed size 1. So the array size is 0 and capacity is 1. Lets perform add operations as below.

• After insert element 10, size is 1 and capacity is 1
• As array is full, before inserting 20 create new array with double the current capacity which is 2 and copy over elements from old array to newly created array. Going forward newly created array is the one we are going to use as our array. Now size becomes 2.
• As array is full, same way expand the array and now size is 3 and capacity is 4
• Array is not full, so insert 40 at last index.
• After inserting 40, array size is 4 and capacity is 4.

• As array is full , before inserting next element 50, again create new array whose capacity is double the current capacity which is 8 and copy over the elements from old array to newly created array and change array reference to newly created array.

Video Explanation

Delete / Remove

1int delete(): 
2    // if no elements left in the array throw error   
3    if size <= 0 throw error  
4
5    // copy the element at last index which is size-1 
6    int data = array[size-1]  
7
8    // remove the last element by reducing the size by 1 
9    size = size - 1       
10
11    // if only 1/4 of the array is used   
12    if size == capacity/4   
13
14    // shrink the array to 1/2 the capacity  
15    resize(capacity/2)    
16
17    // finally return the deleted element       
18    return data  

The below diagram shows how arrays shrinks dynamically :

After performing insert operations, now we have the array with size 5 and capacity 8.

• After deleting 50, array size becomes 4 which is half of array's capacity. We are not shrinking here as if we get insert operation we again need to resize the array to insert new value.
• After deleting 40, array size becomes 3.
• After deleting 30, array size becomes 2 which is 1/4 of the array’s capacity. So we can shrink the array by to 1/2 of the current capacity.
• So we create a new array of size 4 and copy over the elements from the original array to newly created array and update the array reference to newly created array.

Video Explanation

Java Implementation

1public class DynamicArray {
2
3    private int[] array;
4    private int capacity;
5    private int size;
6
7    // constructor to initial capacity of the dynamic array as 1
8    public DynamicArray(){
9        this(1);
10    }
11
12    public DynamicArray(int initialCapacity) {
13        this.capacity = initialCapacity;
14        array = new int[initialCapacity];
15        size = 0;
16    }
17
18    // method to add element at end of the array
19    public void add(int ele){
20        // if array is full
21        // grow the array by doubling the capacity
22        if(isFull()) {
23            resize(2*capacity);
24        }
25        // insert element at empty position which is at index size
26        array[size++] = ele;
27    }
28
29    public int delete(){
30        // if array is empty, return invalid value
31        if(isEmpty()){
32            return -1;
33        }
34        // get the last element which has to be deleted
35        int data = array[--size];
36        array[size] = 0;
37        // after delete if array has occupied just 1/4 of its capacity
38        // shrink the size to half
39        if(size == capacity/4) {
40            resize(capacity/2);
41        }
42        return data;
43    }
44
45    // method to check array is full or not
46    private boolean isFull(){
47        return capacity == size;
48    }
49
50    // method to check array is empty or not
51    private boolean isEmpty(){
52        return size == 0;
53    }
54
55    // method to grow or shrink the array
56    private void resize(int newCapacity){
57        int[] newArray = new int[newCapacity];
58        for(int i=0; i< size; i++) {
59            newArray[i] = array[i];
60        }
61        capacity = newCapacity;
62        array = newArray;
63
64    }
65
66    // method to print elements in the array
67    public void print(){
68        for(int i=0;i<size;i++){
69            System.out.print(array[i] + "  ");
70        }
71        System.out.println("  size is "+size +"  capacity is "+capacity);
72    }
73
74    // driver method
75    public static void main(String[] args) {
76        DynamicArray obj = new DynamicArray();
77        System.out.print("Add 10   :     ");
78        obj.add(10);
79        obj.print();
80
81        System.out.print("Add 20   :     ");
82        obj.add(20);
83        obj.print();
84
85        System.out.print("Add 30   :     ");
86        obj.add(30);
87        obj.print();
88
89        System.out.print("Add 40   :     ");
90        obj.add(40);
91        obj.print();
92
93        System.out.print("Add 50   :     ");
94        obj.add(50);
95        obj.print();
96
97        System.out.print("Add 60   :     ");
98        obj.add(60);
99        obj.print();
100
101        System.out.print("Add 70   :     ");
102        obj.add(70);
103        obj.print();
104
105        System.out.print("Add 80   :     ");
106        obj.add(80);
107        obj.print();
108
109        System.out.print("Add 90   :     ");
110        obj.add(90);
111        obj.print();
112
113        for(int i=0; i<8; i++){
114            System.out.print("Deletion :     ");
115            obj.delete();
116            obj.print();
117        }
118    }
119}

Video Explanation