![Amazon Prime](https://technologystrive.com/images/amazonPrime.jpg)
Dynamic Array
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] = 103array[1] = 204array[2] = 305array[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 size2 example : int[] newArray = new int[10] // 2*5 (double the original size)34Step2: copy all values of array into new array5 for i : 0 to 4 newArray[i] = array[i]67Step3: Now update array to newArray8 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) :23 capacity = newCapacity45 // newCapacity is decided based on grow (during add)6 // or shrink (during delete) operation7 int[] newArray = new int[newCapacity]89 for i-> 0 to size-110 // copy elements from the original array to newly created array11 newArray[i] = array[i]1213 // Newly created array will be considered as the original array14 array = newArray
Add / Insert
1 void add(int ele) :2 // If the array is full3 if size == capacity4 resize(2*capacity)56 // insert element7 array[size] = ele89 // increment size10 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 error3 if size <= 0 throw error45 // copy the element at last index which is size-16 int data = array[size-1]78 // remove the last element by reducing the size by 19 size = size - 11011 // if only 1/4 of the array is used12 if size == capacity/41314 // shrink the array to 1/2 the capacity15 resize(capacity/2)1617 // finally return the deleted element18 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 {23 private int[] array;4 private int capacity;5 private int size;67 // constructor to initial capacity of the dynamic array as 18 public DynamicArray(){9 this(1);10 }1112 public DynamicArray(int initialCapacity) {13 this.capacity = initialCapacity;14 array = new int[initialCapacity];15 size = 0;16 }1718 // method to add element at end of the array19 public void add(int ele){20 // if array is full21 // grow the array by doubling the capacity22 if(isFull()) {23 resize(2*capacity);24 }25 // insert element at empty position which is at index size26 array[size++] = ele;27 }2829 public int delete(){30 // if array is empty, return invalid value31 if(isEmpty()){32 return -1;33 }34 // get the last element which has to be deleted35 int data = array[--size];36 array[size] = 0;37 // after delete if array has occupied just 1/4 of its capacity38 // shrink the size to half39 if(size == capacity/4) {40 resize(capacity/2);41 }42 return data;43 }4445 // method to check array is full or not46 private boolean isFull(){47 return capacity == size;48 }4950 // method to check array is empty or not51 private boolean isEmpty(){52 return size == 0;53 }5455 // method to grow or shrink the array56 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;6364 }6566 // method to print elements in the array67 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 }7374 // driver method75 public static void main(String[] args) {76 DynamicArray obj = new DynamicArray();77 System.out.print("Add 10 : ");78 obj.add(10);79 obj.print();8081 System.out.print("Add 20 : ");82 obj.add(20);83 obj.print();8485 System.out.print("Add 30 : ");86 obj.add(30);87 obj.print();8889 System.out.print("Add 40 : ");90 obj.add(40);91 obj.print();9293 System.out.print("Add 50 : ");94 obj.add(50);95 obj.print();9697 System.out.print("Add 60 : ");98 obj.add(60);99 obj.print();100101 System.out.print("Add 70 : ");102 obj.add(70);103 obj.print();104105 System.out.print("Add 80 : ");106 obj.add(80);107 obj.print();108109 System.out.print("Add 90 : ");110 obj.add(90);111 obj.print();112113 for(int i=0; i<8; i++){114 System.out.print("Deletion : ");115 obj.delete();116 obj.print();117 }118 }119}