A dynamic array is a sequential data structure that behaves the same as a native array only that it allows growing CAPACITY. In order to support this feature it needs to maintain a native array underneath and keep track of CAPACITY and list SIZE. C++ structure:
template<typename T>
class ArrayList {
...
private:
T* contents;
std::size_t capacity;
std::size_t size;
};
As you can notice in animation below, by virtue of being an expandable native array, it supports random access and both forward and backward traversal (HEAD ⇄ TAIL)! For a complete implementation example, check ArrayList class documentation or its GitHub code.
A native array is a memory block allocated in RAM of CAPACITY size where every element is accessible by position index inside block. Because they are preallocated when program is compiled and lookups only require navigating within same block, native arrays are very fast but they also have a major disadvantage in being too rigid: they cannot expand when CAPACITY is reached.
Let's say we allocate a NATIVE ARRAY with 8 elements CAPACITY then feed it with 11 values:
To solve this problem, dynamic arrays were created: whenever entries are added and CAPACITY is reached, latter grows by doubling its size in order to accomodate the new data. Operating system offers a realloc native C function that performs this task by trying to expand same memory block to desired CAPACITY:
Let's say we allocate a DYNAMIC ARRAY with 8 elements initial CAPACITY then feed it with 11 values:
As a high performance sequential data structure, dynamic array can be used to implement many abstract data types. Let us take its List implementation as an example to understand how it works:
| Operation | Description |
| addToHead | Inserts VALUE at position zero, moving all entries in memory block one step to the right then increments SIZE. If CAPACITY is reached, memory block grows by doubling its size. |
| addToTail | Adds entry at SIZE position then increments SIZE If CAPACITY is reached, memory block grows by doubling its size. |
| clear | Frees memory block from RAM, reallocates it for same CAPACITY, resets SIZE to zero. |
| containsIndex | Checks if position is smaller than SIZE. |
| containsValue | Loops for all entries in memory block and checks if one equals VALUE by COMPARATOR. |
| emplace | Inserts VALUE at POSITION, moving all entries in memory block found at greater/equal POSITION one step to the right then increments SIZE. If CAPACITY is reached, memory block grows by doubling its size. |
| get | Navigates to POSITION in memory block and returns VALUE stored inside. |
| set | Navigates to POSITION in memory block and changes value inside to VALUE. |
| removeIndex | Navigates to POSITION in memory block, moving all entries in memory block found at greater/equal POSITION one step to the left then decrements SIZE. |
| removeValue | Removes all values that match VALUE by COMPARATOR, moving all entries in memory block found at that POSITION one step to the left then decrements SIZE. |
| isEmpty | Checks if SIZE equals zero |
| size | Gets SIZE value |
As one can notice, if SIZE decreases further and further, memory block is not shrinked. Even though this is possible, few if any DYNAMIC ARRAY implementations do it because of performance implications!
To understand why, let's say you create a dynamic array with 8 elements capacity. When you insert the 9-th, array grows at 16 but if you delete it back it would shrink back to 8. If this scenario repeats again and again adding/removing 9th element would become a performance bottleneck because any igrowing/shrinking costs CPU time!
Overall, dynamic array comes with both huge advantages and huge disadvantages: