Dynamic Array Data Structure

Dynamic arrays are a type of data structure that offer a flexible and efficient way to manage collections of elements. Unlike static arrays, which have a fixed size determined at the time of their creation, dynamic arrays can grow or shrink in size as needed, which is helpful in scenarios where the number of elements is not known in advance. They provide the convenience of array-like indexing of stored elements, with the added benefit of dynamic resizing.

Why use dynamic arrays?

Static arrays offer simplicity and potentially faster access due to their fixed size in memory. However, since their size is determined at creation, adding elements to the same array beyond it’s initial capacity becomes impossible. To overcome this limitation, you will need to:

Create a new static array with a larger size to accommodate the additional element.
Copy all the existing elements from the old array to the new one.
Add the new element to the new array’s available space.

This process of re-creating a new array with bigger size and copying elements can be time-consuming and memory-intensive. Also any code directly accessing the old array’s memory location wouldn’t work as expected.

Dynamic arrays handle by efficiently resizing and managing memory allocation whenever elements are added or removed.

Internals of a Dynamic Array

Dynamic arrays use a fixed-size array as an underlying storage mechanism. When this underlying array fills up, a new, larger array is allocated, then the existing elements are copied over and finally the new elements are added. Whenever resizing has to be done, the internal array is re-sized to a size more than what is actually required. This makes sure that the re-sizing operation is not required for every element added to the dynamic array.

Array re-sizing techniques

There are a few common re-sizing approaches like:

Doubling the Array Size: When the array reaches its capacity, a new array with double the size is created, and existing elements are copied over. This offers a good balance between memory efficiency and minimizing the number of resizes.
Using a Growth Factor: The array is resized by a multiplicative factor (e.g., 1.5x or 2x). This sometimes might lead to less frequent resizes and memory consumption when compared to doubling.
Increasing by a Fixed Amount: The array’s size is increased by a fixed number of elements (e.g., 10) each time it becomes full. While the simplest, this approach leads to frequent resizes if the increase amount is less, potentially impacting performance.

Most common implementations of dynamic arrays mostly double the array size every time the array fills up. Some implementations increase the array by a factor of 1.5 everytime a resize is required.

Operations on Dynamic Arrays

Appending an Element: Appending to the end of a dynamic array usually has a constant time complexity (O(1)). Occasionally, if the underlying array is full, a resize operation is necessary which has O(N) time complexity.
Inserting an Element: Inserting at a specific index may require shifting elements to make room, leading to a potential time complexity of O(N), where ‘N’ is the number of elements.
Removing an Element: Similar to insertion, removing elements may involve shifting to fill the gap, potentially resulting in O(N) time complexity.
Accessing an Element: Dynamic arrays offer direct access by index with a constant time complexity of O(1).

In-built Dynamic Arrays

Java: The ArrayList class provides dynamic array functionality.
C++: The vector class from the Standard Template Library (STL) acts as a dynamic array.
Python: Python lists are inherently dynamic arrays.

Below are few examples of how to use them in different programming languages:


# Declare a dynamic array
dynamic_array = []

# Add numbers to the dynamic array
for num in [0, 1, 2, 4, 5]:
  dynamic_array.append(num)

# Remove number at index 2
del dynamic_array[2]

# Add number 24 at index 1
dynamic_array.insert(1, 24)

# Access element at index 3
print(dynamic_array[3])


#include <vector>

int main() {
  // Declare a dynamic array
  std::vector<int> dynamic_array;
  
  // Add numbers to the dynamic array
  dynamic_array.push_back(0);
  dynamic_array.push_back(1);
  dynamic_array.push_back(2);
  dynamic_array.push_back(4);
  dynamic_array.push_back(5);
  
  // Remove number at index 2
  dynamic_array.erase(dynamic_array.begin() + 2);
  
  // Add number 24 at index 1
  dynamic_array.insert(dynamic_array.begin() + 1, 24);
  
  // Access element at index 3
  int element = dynamic_array[3];
}


import java.util.ArrayList;

public class Main {
  public static void main(String[] args) {
    // Declare dynamic array
    ArrayList<Integer> dynamic_array = new ArrayList<>();

    // Add numbers to the dynamic array
    dynamic_array.add(0);
    dynamic_array.add(1);
    dynamic_array.add(2);
    dynamic_array.add(4);
    dynamic_array.add(5);

    // Remove number at index 2
    dynamic_array.remove(2);

    // Add number 24 at index 1
    dynamic_array.add(1, 24);

    // Access element at index 3
    int element = dynamic_array.get(3);
    System.out.println(element);
  }
}

Advantages of Dynamic Arrays

Flexibility: Dynamic arrays solve the issue of needing to know the exact size of data beforehand.
Memory Efficiency: Dynamic arrays allocate memory optimally as per usage, avoiding large chunks of unused space.
Ease of Use: Most programming languages provide dynamic array implementations, making them easy to work with instead of manually writing the logic for resizing static arrays.

Applications of Dynamic Arrays

Variable-Sized Collections: When the number of items to store is unpredictable, dynamic arrays are ideal.
Building Blocks: Dynamic arrays are used to implement higher-level data structures like stacks, queues, and hash tables (under certain implementations).
Caching and Buffering: Dynamic arrays are useful for temporary data storage where the size may fluctuate.