In this article, we are going to understand what a dynamic array is, the features of the dynamic array, the strengths and weaknesses of a dynamic array, and how to implement a dynamic array in Java.
1. What is a Dynamic Array?
To understand what a dynamic array is, we must first know what is an array. In data structures, the array is a fixed size data structure and we can’t change the size of the array after declaring it initially. So, if we have declared an integer array with an initial size of 5, we can’t insert the 6th integer element in it as we don’t have space for it.
To overcome this limitation of the array, programmers use dynamic array. Dynamic array expands the size of the array on the run time when you try to insert an element after the initial capacity is over. We can add and remove elements as per our business logic and the dynamic array will handle it automatically. The extra memory allocation happens using the heap memory.
If we take an example in Java, the ArrayList is a dynamic array. It resizes itself based on the requirement. C++ has a Vector data structure for the same purpose.
1.1 Strengths of Dynamic Array
- Retrieving an element from a given index is done in
O(1)time. - We can add as many elements as we need as long as we have memory left in the heap to assigned to our array.
- Since dynamic arrays place items right next to each other in memory, it is thus cache-friendly.
1.2. Weaknesses of Dynamic Array
- If we are appending to an array that doesn’t have any spaces left, it will create a new array, copy existing elements, and then add new ones.
- Insert and remove from the middle of the array is very costly as it requires shifting. The reason being elements are stored adjacent to each other in memory. So, in the worst case, it will take
O(n)time for these operations.
2. Size vs Capacity in Dynamic Array
Let us understand the difference between dynamic array size and capacity. When we first create and initialize the dynamic array, we create a fixed-sized array. For example, let’s say we have created a dynamic array to store 10 elements and say we have added 5 elements to it. Now, the dynamic array has 5 elements though the underlying data structure’s length is 10. So here the size of the array would be 5 and the capacity of the array would be 10.Below is the picture depicting this process:
3. Dynamic Array Key Features
On a high level, dynamic array provides the following three main features:
- Add element to the array.
- Remove element.
- Dynamic resizing
3.1. Add Element to Dynamic Array
Let’s start with an array with an initial size of 5 and add 5 elements. When we try to insert the 6<sup>th</sup> element, usually a new array will be created with the size of 10 (double of existing array size), with that, it will copy the existing elements in the new array and also insert the new element at the last. The old array’s memory would be garbage collected and existing elements would have a new memory location. We will use method addElement(int element) for this.
We can also insert an element at a given index using public void addElement(int index, int element), It will shift the remaining elements (elements that are right to the added element) to the right from the specified index.
3.2. Remove an Element
We can remove the elements from a dynamic array using remove() and removeAt(i) methods. The remove method will remove the last element from the array and place 0 there. The removeAt(i) method will remove the i<sup>th</sup> (array index starts at 0) element from the array. It will shift the remaining elements (elements that are right to the deleted element) to the left from the specified index.
3.3. Resizing Dynamic Array
There are two use cases when we will be resizing our array. First, when our array has more memory than required. Second, when our array doesn’t have space to add a new element.For the first case, we will use the trimToSize() method in the code below to shrink the array. It will free up the unused heap memory for other objects.
For the second case, we will use the increaseCapacity()method to increase the capacity of our array two times. We have already seen the weakness of dynamic array when we add element after the initial capacity is over as it will create a new array of double size and copy the elements.
Now if you wish to add another element in the above-trimmed array, we will use increaseCapacity() method to double the size of the array.Here is how the increaseCapacity () method will work
4. Time ans Space Complexity for Dynamic Array
Dynamic Arrays are good data structure when it comes to search operation. It takes O(1) in both avg and worst case. Here is the time and complexity chart for the dynamic array.
| Average Case | Worst case | |
| Insert | O(n) | O(n) |
| Delete | O(n) | O(n) |
| Append | O(1) | O(n) |
| Lookup/ Search | O(1) | O(1) |
| Space | O(n) | O(n) |
5. Amortized Analysis of Dynamic Array
There are two scenarios when we add an element to a dynamic array, first, when array has the space, so the time complexity is O(1). Second, when there is no space left, so the time complexity would be O(N) (n is the number of elements in the array).
The amortized(average) cost to add an element to dynamic array will depend on how frequently do we resize and when we resize, there are two options:
- Increase the size by a constant k (size will increase like k,2k,3k…). The process of copying over all of the elements while resizing takes
O(N^2)time. Dividing this by theN+1appends, the amortized cost for each such operation will be –O(N^2)/{N+1} =~ O(N). - Increase the size by a constant factor k.The process to copy the elements while resizing only takes O(N)) time. Dividing this by the N+1 appends, the amortized cost for each such operation will be:
O(N)/{N+1} =~ O(1).
6. Implementing a Dynamic Array in Java
We covered the basic of dynamic array which includes:
- What are dynamic array?
- How do the dynamic arrays works?
- What are the different features of dynamic array.
Let’s implement the dynamic array in Java to get a better understanding of the working.The code contains detailed documentation to explain the key concepts but feel free to leave a comment in case you have ay questions or queries.
package arrays;
import java.util.Arrays;
public class MyDynamicArray {
private int array[];
private int size;
private int capacity;
/**
* Constructor with initial capacity of 2
*/
public MyDynamicArray() {
array = new int[2];
size = 0;
capacity = 2;
}
/**
* check for capacity and if there is capacity add the element at the end of the array.
* @param element
*/
public void addElement(int element) {
if (size == capacity) {
try {
increaseCapacity(2);
} catch (Exception e) {
System.out.println("unable to increase the capacity of the array");
e.printStackTrace();
}
}
array[size++] = element;
}
/**
* Adding element at a given index
* @param index
* @param element
*/
public void addElement(int index, int element) {
//check if the array has capacity to add element.
if (size == capacity) {
try {
increaseCapacity(2);
} catch (Exception e) {
System.out.println("unable to increase the capacity of the array");
e.printStackTrace();
}
}
// shift all elements from the given index to right
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
}
// insert the element at the specified index
array[index] = element;
size++;
}
/**
* get an element from given index, O(1) time complexity
* @param index
* @return
*/
public int getElement(int index) {
return array[index];
}
/**
* Remove an element at the last index
*/
public void remove() {
if (size > 1) {
array[size--] = 0;
}
}
/**
* Remove an element from given index
* @param index
*/
public void removeAt(int index) {
if (index >= size || index < 0) {
System.out.println("No element at this index");
} else { //shifting
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
array[size - 1] = 0;
size--;
}
}
/**
* If there is no place to insert a new element,
* double the capacity for the array by creating
* a new array and copy exiting elements.
* @param minCapacity
*/
public void increaseCapacity(int minCapacity) {
int tempArray[] = new int[capacity * minCapacity];
for (int i = 0; i < capacity; i++) {
tempArray[i] = array[i];
}
array = tempArray;
capacity = capacity * minCapacity;
}
/*
* Trim the capacity of dynamic array to the current size. i.e. remove unused space
*/
public void trimToSize() {
System.out.println("Trimming the array");
int tempArray[] = new int[size];
//we can use libraries as well to copy the array elements to temparray.
for (int i = 0; i < size; i++) {
tempArray[i] = array[i];
}
array = tempArray;
capacity = array.length;
}
/**
* return the size of the array
* @return
*/
public int getSize() {
return this.size;
}
/**
* return the capacity of the array
* @return
*/
public int getCapacity() {
return this.capacity;
}
/**
* Print the array elements
*/
public void printElements() {
System.out.println("elements in array are :" + Arrays.toString(array));
}
/**
* main method
* @param args
*/
public static void main(String args[]) {
MyDynamicArray array = new MyDynamicArray();
// adding two elements to the array
array.addElement(1);
array.addElement(2);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.addElement(3);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
// add element at index 1
array.addElement(1, 5);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
// add element at index 2
array.addElement(2, 6);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.removeAt(2);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.removeAt(2);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.removeAt(1);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.removeAt(2);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.removeAt(1);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
// Trim the array
array.trimToSize();
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.addElement(2);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
array.addElement(3);
System.out.println("The array size is :" + array.getSize() + " and the array capacity is :" + array.getCapacity());
array.printElements();
}Output
7. When to use Fixed Array vs Dynamic Array
We use fixed-size array when we are sure about the capacity of the array from the beginning and you know that you will not require it to change during the course of the program. For example, if you wish to store the name of the months, you can use a fixed sized array with capacity of 12 as you know that names of the month won’t change.
We use dynamic array when we are not sure about the capacity of the array from the beginning and it might change during the course of the program. Dynamic array gives us the flexibility to add more elements once the initial capacity is over and does it automatically.
Summary
In this article, we covered the dynamic array data structure and it’s different characteristics. To summarize
- We have learned array and dynamic array.
- We have learned the strengths and weaknesses of the dynamic array.
- We have understood the features of the dynamic array.
- We have learned about time and space complexities of dynamic array.
- We have seen the amortized analysis of the dynamic array.
- We have seen the pictorial representation all the operations as well.
- We have developed a java code on how the dynamic array works.
As always the source code for this article is available on our GitHub repository
