Data Structures: Dynamic Arrays

What is a dynamic array?

A dynamic array is a sequential data structure very similar to a native array. 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.

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 native C function (realloc) that performs this task, trying to expand same memory block to desired CAPACITY. If that is possible, program suffers almost no performance penalty and dynamic array is virtually as fast as a native one. If not, however, operating system needs to move the memory block to a new place in RAM that allows expansion to desired CAPACITY. When that happens, program suffers a performance penalty because data was moved in RAM.

How does it work?

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!

Overall, dynamic array comes with both huge advantages and huge disadvantages:


Share