Dynamic Array is a growable, resizable, linear collection of elements of the same type that allows elements to be accessed, added and removed. In other words, the dynamic array is a basic array that has been taken a step further. It presents some more functionality compared to basic arrays. Whenever a dynamic array gets full, it is capable of resizing itself so that it is possible to add new elements, or when many of its elements are removed, it is able to reduce its capacity so that unused memory is no longer occupied.
It is handy to use Dynamic Arrays when it is needed to add new elements, remove elements, and at the same time provide random element access for constant time — O(1).
public class DynamicArray<T> {
public T [] array;
public int count;
public int capacity;
public Class<T> tClass;
public DynamicArray(Class<T> tClass) {
this.tClass = tClass;
this.count = 0;
this.capacity = 16;
array = (T[]) Array.newInstance(tClass, capacity);
}
}The code above shows a sample structure of Dynamic Array class. T[] array is the array that stores all elements added, count — is the number of elements that have been added to the array so far, capacity — is the size of the array i.e. it indicates how many elements can be added, tClass — is the specific data type that shows what kind of data can be added. If tClass is String, the array will be a collection of String, if tClass is Integer, then, a collection of integers. When a dynamic array is initialized, count — is always 0, capacity is usually by default is 10 or 16. The value of capacity varies and depends on the implementation.
Dynamic Array provides the following operations — add(item),
add(index, item), remove(item), get(index). The time complexities of the operations provided by DynamicArray are as follows:
Add — O(N)
Remove — O(N)
Get — O(1)
In the next sections, we will discuss all the following operations in detail and how they are implemented.
Adding a new item / element — add(item) is implemented in a pretty straightforward way as demonstrated. Initially, when the array initialized, the number of added items, or count, is equal to 0. When an item is added for the first time, the item is put into the first position with index =0 and count is incremented by 1. Each time while adding a new item, count is incremented by 1, i.e. count + 1. Interim result: count = 1.
array[count] = item;
count++;When we add a consequent item, the index of the position we put the item into is always equal to count. This process goes the same till count, or the number of added elements, is not equal to capacity. When
count == capacity, it means the array is full and there is no space for new elements. In this case, we need to re-initialize or re-size our initial array with more capacity so that there is enough space for new elements. Usually, the capacity is increased by one and a half or two times.
capacity = capacity * 2;
array = (T[]) Array.newInstance(tClass, capacity);After re-initializing an array with more capacity, all the values from the original array are copied to a new array, and then a new item is added. When there is space for new elements while adding a new element, the operation is completed pretty fast — O(1), but it requires — O(N) when the array is full.
Overall time complexity of add(item)— O(N).
This is how the operation — add(item) is implemented. (This process of an array re-initializing is shown on the picture, see the operation — add(Tony).
Dynamic Arrays provide one more operation of adding new elements, that is adding to a specified index — add(index, item). The difference is that this operation accepts one more argument , that is — index and puts a new item to that index. While adding a new item into a specified index, the original item with that index is not removed. Add(index, item) is implemented in the following way — firstly, all the original items shift forward to one index, and then a new item is added into a specified index. Each time while adding a new item, count is incremented by 1, i.e. count + 1.
However, it is important to use this operation carefully. All the items in the array are placed consequently, it is an error to leave free position between items, so that specifying a right index is important.
Examples:
If the array is empty, then the specified index must be 0, any other index, otherwise, is an error.
If there are eight items in the array, as illustrated on the above picture, the allowed index bound is [0–8], in case index=8, the item will be added right after the last item, in case index=9, it will cause an error, since index=8 is empty.
Removing or deleting an item — remove(item) is implemented in the following way. Removing an item is done using the index of an item. It is important to specify the right index. Removing an item causes changes inside the array as well. Since there must not be empty positions between the items in the array, all the items after the specified index shift backwards to one index and decrement. While removing an item, the item with the specified index is replaced by the next coming item in the array and so on.Each time while removing an item, count is decremented by 1, i.e. count -1.
Importantly, after a series of item removals, there maybe be a need to reduce the array capacity, in case of many empty positions in order to use memory efficiently. While reducing an array capacity, all the original items are copied to a new array with a fewer capacity. Generally, an array capacity is reduced by one and half times(=1,5).
Overall time complexity of remove(index)— O(N)
Array Capacity reducing is done, if the following condition is met:
May count — is the number of elements in the array, capacity — is the max number of elements that can be added to the array, defaultCapacity — the initial and minimum array capacity. Then,
If count < capacity / 2, then capacity = capacity / 1,5.
If capacity < defaultCapacity, then capacity = defaultCapacity
To put it simply, if count is less than capacity divided by two, then capacity is reduced by one and a half times. However, if capacity is less than defaultCapacity, then defaultCapacity is set to capacity.
Example:
May defaultCapacity=6, count=5, capacity=12, then
count < capacity / 2 ? -> Yes. Then, capacity = 12 / 1,5 -> capacity = 8.
Besides, if capacity < defaultCapacity ? -> Yes, then,
capacity = defaultCapacity = 8.
Trying to remove an item with a wrong index causes an error, or exception. As illustrated above, it is essential to specify the right index.
Getting or retrieving an item — get(index) is implemented pretty easily compared to other operations. Since we have instant access to all the items of the array, we just return the item by addressing its index. Time complexity of get(index) — O(1)
Trying to get an item with a wrong index causes an error as well, as illustrated in the picture.
The next post awaiting us will be about Stacks & Queues — The easiest and pretty efficient data structure.
If you are curious to dive deeper and play around with the DynamicArray, I recommend to implement the discussed operations by yourself and test.
The following are the links for:
Raw code to implement Dynamic Array by yourself
Sample implementation of Dynamic Array
Test cases
