Arrays and Dynamic Arrays
Arrays are the most fundamental data structure in computer science. They store elements in contiguous memory locations, enabling O(1) random access. Dynamic arrays (like Python lists or Java ArrayLists) extend this with automatic resizing.
What is an Array?
An array is a collection of elements stored in contiguous (adjacent) memory locations. Each element is identified by its index, starting at 0.
Because elements are stored contiguously, the memory address of any element can be calculated directly:
address(i) = base_address + i * element_size
This formula enables O(1) random access — you can jump directly to any element without traversing others. This is the defining advantage of arrays over linked structures.
Arrays are fixed-size in most low-level languages (C, C++). The size must be declared at creation and cannot change.
Time Complexity of Array Operations
Understanding the performance characteristics of arrays:
- Access by index — O(1). Direct memory calculation. The fastest possible access.
- Search (unsorted) — O(n). Must check each element in the worst case.
- Search (sorted) — O(log n) with binary search.
- Insert at end — O(1) amortized for dynamic arrays (O(n) when resize occurs).
- Insert at middle/beginning — O(n). Must shift all subsequent elements right.
- Delete at end — O(1). Just decrement the size.
- Delete at middle/beginning — O(n). Must shift all subsequent elements left.
Dynamic Arrays and Amortized Analysis
A dynamic array (Python list, Java ArrayList, C++ vector) automatically resizes when it runs out of space. The key insight is the doubling strategy:
When the array is full and a new element is added: 1. Allocate a new array of double the current size 2. Copy all existing elements to the new array 3. Add the new element
This resize operation is O(n), but it happens rarely. Using amortized analysis, the average cost per insertion is still O(1). Over n insertions, the total work is O(n) — each element is copied at most log2(n) times.
Array Operations in Python
Python lists are dynamic arrays. Here are common operations with their complexities:
# ---- Basic Array Operations ----
arr = [10, 20, 30, 40, 50]
# Access - O(1)
print(arr[2]) # 30
print(arr[-1]) # 50 (last element)
# Slice - O(k) where k is slice size
print(arr[1:4]) # [20, 30, 40]
# Insert at end - O(1) amortized
arr.append(60) # [10, 20, 30, 40, 50, 60]
# Insert at position - O(n) (shifts elements)
arr.insert(2, 25) # [10, 20, 25, 30, 40, 50, 60]
# Delete at end - O(1)
arr.pop() # Removes 60
# Delete at position - O(n) (shifts elements)
arr.pop(2) # Removes 25
# Search - O(n)
print(30 in arr) # True
print(arr.index(30)) # 2
# ---- Implementing a Dynamic Array from scratch ----
class DynamicArray:
def __init__(self):
self._capacity = 1
self._size = 0
self._data = [None] * self._capacity
def __len__(self):
return self._size
def __getitem__(self, index):
if not 0 <= index < self._size:
raise IndexError("Index out of range")
return self._data[index]
def append(self, value):
if self._size == self._capacity:
self._resize(2 * self._capacity) # Double capacity
self._data[self._size] = value
self._size += 1
def _resize(self, new_capacity):
new_data = [None] * new_capacity
for i in range(self._size):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_capacity
print(f"Resized to capacity: {new_capacity}")
def __repr__(self):
return str([self._data[i] for i in range(self._size)])
# Test
da = DynamicArray()
for i in range(10):
da.append(i * 10)
print(f"Size: {len(da)}, Capacity: {da._capacity}")Two-Pointer and Sliding Window Techniques
Arrays enable powerful algorithmic patterns:
# ---- Two Pointer: Find pair with target sum (sorted array) ----
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current = arr[left] + arr[right]
if current == target:
return (left, right)
elif current < target:
left += 1
else:
right -= 1
return None
print(two_sum_sorted([1, 3, 5, 7, 9], 12)) # (2, 4) -> 5+7=12
# ---- Sliding Window: Maximum sum subarray of size k ----
def max_sum_subarray(arr, k):
n = len(arr)
if n < k:
return -1
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, n):
window_sum += arr[i] - arr[i - k] # Slide window
max_sum = max(max_sum, window_sum)
return max_sum
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9 (5+1+3)Key Takeaways
- Arrays store elements in contiguous memory, enabling O(1) random access by index.
- Dynamic arrays use a doubling strategy to resize, giving O(1) amortized append performance.
- Insertion and deletion in the middle are O(n) due to element shifting.
- Two-pointer and sliding window patterns leverage array indexing for efficient O(n) algorithms.
- Choose arrays when you need fast random access; choose linked lists when you need fast insertion/deletion.
Contact Us
Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com