Arrays: Memory & Operations
Understand memory representation and implement traversal, insertion, and deletion in arrays.
Arrays: Memory & Operations
An array is the most fundamental data structure - a contiguous block of memory storing elements of the same type.
Memory Representation
``
Index: 0 1 2 3 4
Value: [10] [20] [30] [40] [50]
Addr: 100 104 108 112 116 (4 bytes per int)
`
Address formula: addr(i) = base_addr + i × size_of_element
This gives O(1) random access - the killer feature of arrays.
Array Operations
Header Operation Time Why
Header Access by index O(1) Direct address calculation Search (unsorted) O(n) Must check each element Search (sorted) O(log n) Can use binary search Insert at end O(1) Amortized for dynamic arrays Insert at position O(n) Must shift elements right Delete at position O(n) Must shift elements left Traverse O(n) Visit every element
Insertion at Position i
`
Before: [10, 20, 30, 40, 50] Insert 25 at index 2
Step 1: Shift 50 → [10, 20, 30, 40, _, 50]
Step 2: Shift 40 → [10, 20, 30, _, 40, 50]
Step 3: Shift 30 → [10, 20, _, 30, 40, 50]
Step 4: Place 25 → [10, 20, 25, 30, 40, 50]
`
Deletion at Position i
`
Before: [10, 20, 25, 30, 40, 50] Delete index 2
Step 1: Remove 25 → [10, 20, _, 30, 40, 50]
Step 2: Shift 30 → [10, 20, 30, _, 40, 50]
Step 3: Shift 40 → [10, 20, 30, 40, _, 50]
Step 4: Shift 50 → [10, 20, 30, 40, 50, _]
``
Key Insight
Arrays trade fast access (O(1) index) for costly modifications (O(n) insert/delete). This trade-off is why we need linked lists, stacks, and queues.
Code Example
# Array operations in Python
class DynamicArray:
def __init__(self):
self.capacity = 2
self.size = 0
self.data = [None] * self.capacity
def get(self, index):
if index < 0 or index >= self.size:
raise IndexError("Index out of bounds")
return self.data[index]
def append(self, value):
if self.size == self.capacity:
self._resize(2 * self.capacity)
self.data[self.size] = value
self.size += 1
def insert(self, index, value):
if self.size == self.capacity:
self._resize(2 * self.capacity)
for i in range(self.size, index, -1):
self.data[i] = self.data[i - 1]
self.data[index] = value
self.size += 1
def delete(self, index):
for i in range(index, self.size - 1):
self.data[i] = self.data[i + 1]
self.size -= 1
def _resize(self, new_cap):
new_data = [None] * new_cap
for i in range(self.size):
new_data[i] = self.data[i]
self.data = new_data
self.capacity = new_cap
def __str__(self):
return str(self.data[:self.size])
arr = DynamicArray()
for v in [10, 20, 30, 40, 50]:
arr.append(v)
print(arr) # [10, 20, 30, 40, 50]
arr.insert(2, 25)
print(arr) # [10, 20, 25, 30, 40, 50]
arr.delete(2)
print(arr) # [10, 20, 30, 40, 50]Practice Problems
- 01Implement insert and delete operations on a static array
- 02Build a dynamic array (like Python list) with automatic resizing
- 03Reverse an array in-place using two pointers