Skip to Content

Dynamic Array

What is Dynamic Array?

Dynamic Array is a resizable array that can grow and shrink in size. It is an array that can dynamically adjust its size during runtime, allowing for more flexibility compared to a static array, which has a fixed size. Usually, when the array reaches its capacity, it will allocate a new array with a larger size (usually double the current size) and copy the elements from the old array to the new one.

OperationBig-O TimeNotes
AccessO(1)-
Insert/Remove EndO(1)-
Insert/Remove MiddleO(n)You have to shift the values

Dynamic Array Implementation

For this dynamic array implementation, I will only mention how the resize and insertion operation works, as the other operations are similar to static array implementation.

Insert into Dynamic Array

When we insert a new element into the dynamic array, we will first check if the current length of the array is equal to its capacity. If it is, we will resize the array by creating a new array with double the capacity and copying all the elements from the old array to the new one. After that, we can insert the new element at the end of the array or in the middle and increment the length.

# count = len(dynamic_array) --- track the current number of elements # capacity = len(dynamic_array) def insert(index: int, value: int) -> None: if count == capacity: resize() # Shift elements to the right for i in range(count, index, -1): dynamic_array[i] = dynamic_array[i - 1] # Insert the new element and increment the count dynamic_array[index] = value count += 1

Resize the array

When we resize the array, we will create a new brand array and this new brand array will have new space allocated for it in memory. Then, all the array elements will be copied from the old array to new array, and the old array will be deallocated (free this from memory).

# count = track the current number of elements # capacity = len(dynamic_array) def resize() -> None: capacity = capacity * 2 new_array = [None] * capacity for i in range(count): new_array[i] = dynamic_array[i] dynamic_array = new_array

Dynamic Array Class Implementation

dynamic_array.py
class DynamicArray: def __init__(self, capacity: int = 4): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("Capacity must be a positive integer.") self._items = [None] * capacity # initial allocation self._capacity = capacity self._count = 0 # Track the current number of elements def __len__(self) -> int: return self._count def __getitem__(self, index: int) -> int: if not 0 <= index < self._count: raise IndexError("Index out of bounds.") return self._items[index] def __setitem__(self, index: int, value: int) -> None: if not 0 <= index < self._count: raise IndexError("Index out of bounds.") self._items[index] = value def append(self, value: int) -> None: if self._count == self._capacity: self._resize() self._items[self._count] = value self._count += 1 def insert(self, index: int, value: int) -> None: if not 0 <= index <= self._count: raise IndexError("Index out of bounds.") if self._count == self._capacity: self._resize() for i in range(self._count, index, -1): self._items[i] = self._items[i - 1] self._items[index] = value self._count += 1 def remove(self, index: int) -> int: if not 0 <= index < self._count: raise IndexError("Index out of bounds.") # Store the value to be returned value = self._items[index] # Shift all elements from the next index to the left for i in range(index, self._count - 1): self._items[i] = self._items[i + 1] self._items[self._count - 1] = None self._count -= 1 return value def traverse(self) -> None: for i in range(self._count): print(self._items[i], end=' ') print() def _resize(self) -> None: self._capacity = self._capacity * 2 new_array = [None] * self._capacity for i in range(self._count): new_array[i] = self._items[i] self._items = new_array # Example usage my_array = DynamicArray() my_array.append(1) my_array.append(2) my_array.append(3) my_array.append(4) my_array.traverse() # Output: 1 2 3 4 my_array.insert(1, 5) my_array.traverse() # Output: 1 5 2 3 4 my_array.remove(2) my_array.traverse() # Output: 1 5 3 4

Dynamic Array Visualization

Dynamic Array Visualization (32-bit Integers)
0x2000
[0]
15
0x2004
[1]
32
0x2008
[2]
7
0x200C
[3]
48
Array Length: 4 | Capacity: 4 | Each cell: 4 bytes (32-bit integer) |
Read
Traverse
Insert
Delete
Array is at full capacity. Next insertion will trigger automatic resize (double capacity).
Animation Controls
Array Operations

Will auto-resize to capacity 8

Will auto-resize to capacity 8

Last updated on