Arrays and dynamic arrays

Arrays are one of the most fundamental data structures, widely used for storing ordered elements. Here, we’ll dive into the differences between static and dynamic arrays and see how dynamic arrays are implemented.

Static vs. Dynamic Arrays

Static Arrays

• Fixed Size: Once created, the size of a static array cannot be changed.
• Memory Efficiency: Since the size is fixed, memory is allocated only once, which can be efficient but also wasteful if the array is not filled.
• Contiguous Memory Allocation: Elements are stored in consecutive memory addresses, allowing for fast access.

Dynamic Arrays

• Resizable: Dynamic arrays can grow and shrink at runtime, making them more flexible.
• Automatic Resizing: Typically doubles in size when capacity is reached, although the resizing mechanism varies by implementation.
• Trade-offs in Performance:
• Amortized Cost: Accessing elements is still O(1), but insertion can be O(n) when resizing is needed. However, over time, the cost averages out, making it O(1) amortized.
• Memory Overhead: Often, dynamic arrays allocate extra space to accommodate potential growth, which can lead to some unused memory.

Implementing a Dynamic Array

To implement a dynamic array, we need a few key functions:

1. Resize: Expands the array when it reaches capacity.
2. Add/Insert: Adds a new element, resizing if needed.
3. Remove: Removes an element, resizing if necessary.

Let’s implement a simple dynamic array in Python for illustration.

Python Example: Implementing a Dynamic Array

class DynamicArray:
    def __init__(self):
        self.capacity = 1  # Initial capacity of the array
        self.size = 0      # Number of elements in the array
        self.array = self._create_array(self.capacity)
    
    def _create_array(self, capacity: int) -> list:
        """Creates an empty array with the given capacity."""
        return [None] * capacity
    
    def _resize(self, new_capacity: int):
        """Resizes the array to the new capacity."""
        new_array = self._create_array(new_capacity)
        for i in range(self.size):
            new_array[i] = self.array[i]
        self.array = new_array
        self.capacity = new_capacity
      
    def add(self, element):
        """Adds an element to the dynamic array, resizing if needed."""
        if self.size == self.capacity:
            # Double the capacity
            self._resize(2 * self.capacity)
        self.array[self.size] = element
        self.size += 1
    
    def remove(self, index: int):
        """Removes the element at the specified index and shrinks if necessary."""
        if 0 <= index < self.size:
            for i in range(index, self.size - 1):
                self.array[i] = self.array[i + 1]
            self.array[self.size - 1] = None  # Clear the last element
            self.size -= 1
            # Shrink the array if it's too sparse (e.g., quarter full)
            if self.size <= self.capacity // 4 and self.capacity > 1:
                self._resize(self.capacity // 2)
        else:
            raise IndexError("Index out of range")
    
    def get(self, index: int):
        """Gets the element at the specified index."""
        if 0 <= index < self.size:
            return self.array[index]
        raise IndexError("Index out of range")
        
    def __str__(self):
        return str([self.array[i] for i in range(self.size)])

# Usage Example
dynamic_array = DynamicArray()
dynamic_array.add(1)
dynamic_array.add(2)
dynamic_array.add(3)
print("Array after adding elements:", dynamic_array)
dynamic_array.remove(1)
print("Array after removing element at index 1:", dynamic_array)

Explanation

Initial Capacity: We start with a capacity of 1 and grow the array as needed.

1. Resize Mechanism: _resize() doubles the capacity when the array is full. It also halves the capacity when it’s too sparse (less than a quarter full).
2. Add Operation: add() appends an element and resizes if needed.
3. Remove Operation: remove() removes an element by shifting subsequent elements. It shrinks the array if it’s underutilized.

Access Operation: get() fetches an element at a specific index, throwing an error if the index is out of bounds.