What is a dynamic array?
A dynamic array is a contiguous area of memory whose size grows dynamically as new data is inserted. In static array, we need to specify the size at the time of allocation. If the size of the array is allocated to be 10, we can not insert more than 10 items. However, the dynamic array adjusts it’s size automatically when needed. That means we can store as many items as we want without specifying the size at the time of allocation.
Working of a dynamic array
When we try to insert a new item into the array, we first check if the size is full. If the array is not full, we simply insert the item at the end of the array otherwise we create a new array whose size is double of the current array, we move all the times from old array to new array, we delete the old array to free the memory and finally we insert the item at the end of the expanded array. We start by allocating the array of size 1 and repeat this process when a new item is inserted. Figure 1 shows the insertion process for the first 9 items.
Complexity
We do amortized analysis to find the complexity of the insertion operation (insertion at the end of the array). The normal insertion (when the array is not full) takes the constant time but when the array is full, we need to perform extra work of moving the items into the new array and it takes O(n) time. Since we occasionally do the O(n) operation, the average time of the insertion operation is O(1). Please refer to this link to get the idea of amortized complexity.
Implementation
Most of the programming languages already have the implementation for dynamic arrays. ArrayList
in Java, vector
in C++, list
in Python is an example of a dynamic array. I have implemented a dynamic array in C++ and JAVA which is given below.
1 | // C++ implementation of Dynamic Array |
1 | // Java implementation of Dynamic Array |