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.
No need to specify the array size when initialization.
| Operation | Big-O Time | Notes |
|---|---|---|
| Access | O(1) | - |
| Insert/Remove End | O(1) | - |
| Insert/Remove Middle | O(n) | You have to shift the values |
Advantages
- Dynamic arrays can grow and shrink in size, making them more flexible than static arrays.
- Efficient for accessing elements
Disadvantages
- Resizing can be costly in terms of time and memory
- Insertion and deletion in the middle can be costly as elements may need to be shifted.
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 += 1Resize 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).
Amortized time complexity averages the running times of operations in a sequence over that sequence (average time taken per operation, if you do many operations).
When we resize the array, we will create a new array with double the capacity and copy all the elements from the old array to the new one. This operation takes O(n) time and adding an element takes O(1) time. However, this operation is not performed every time we add an element.
Understands the trade-off
- The O(n) resize operation is expensive but rare.
- The O(1) add-element operation is cheap and frequent.
Therefore, the average time taken per operation is O(1) over a sequence of operations, which is known as amortized time complexity.
# 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_arrayDynamic Array Class Implementation
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 4Dynamic Array Visualization
Will auto-resize to capacity 8
Will auto-resize to capacity 8