Data Structures

Arrays

An array is an ordered collection of elements stored at contiguous memory locations. In Python, the built-in list type is a dynamic array — it resizes automatically as you add or remove elements.

What Is an Array?

Arrays store elements indexed by position. Index access is O(1) because the memory address of any element can be calculated directly: address = base + index × element_size.

Python

# Creating arrays (Python lists)
nums = [10, 20, 30, 40, 50]

# Index access — O(1)
print(nums[0])    # 10  (first element)
print(nums[-1])   # 50  (last element)
print(nums[2])    # 30  (zero-indexed)

# Slicing — O(k) where k is slice length
print(nums[1:4])  # [20, 30, 40]
print(nums[:3])   # [10, 20, 30]
print(nums[::2])  # [10, 30, 50] (every other)

Access & Traversal

Python

fruits = ['apple', 'banana', 'cherry', 'date']

# Traverse with index
for i in range(len(fruits)):
    print(i, fruits[i])

# Traverse with enumerate (Pythonic)
for i, fruit in enumerate(fruits):
    print(i, fruit)

# Reverse traversal
for fruit in reversed(fruits):
    print(fruit)

# Check membership — O(n) for list
print('banana' in fruits)  # True

Insertion

Python

arr = [1, 2, 3, 4, 5]

# Append to end — O(1) amortized
arr.append(6)           # [1, 2, 3, 4, 5, 6]

# Insert at index — O(n): shifts all elements to the right
arr.insert(0, 0)        # [0, 1, 2, 3, 4, 5, 6] — worst case, shift all
arr.insert(3, 99)       # [0, 1, 2, 99, 3, 4, 5, 6] — shifts right half

# Extend with another list — O(k)
arr.extend([7, 8, 9])   # k = len of extension

Removal

Python

arr = [10, 20, 30, 40, 50]

# Remove last element — O(1) amortized
last = arr.pop()        # 50; arr = [10, 20, 30, 40]

# Remove at index — O(n): shifts remaining elements left
first = arr.pop(0)      # 10; arr = [20, 30, 40] — shifts everything

# Remove by value — O(n): search then shift
arr.remove(30)          # arr = [20, 40]

# Clear all — O(n)
arr.clear()

💡

Use deque for efficient front removal

list.pop(0) is O(n) because Python must shift every element. If you need O(1) removal from both ends, use collections.deque instead.

Searching

Python

arr = [3, 1, 4, 1, 5, 9, 2, 6]

# Linear search — O(n)
print(arr.index(5))     # 4 (raises ValueError if not found)
print(5 in arr)         # True

# Find all occurrences — O(n)
indices = [i for i, x in enumerate(arr) if x == 1]
print(indices)          # [1, 3]

# Min / max — O(n) scan
print(min(arr))         # 1
print(max(arr))         # 9

Complexity Table

Operation	Time	Note
Access by index	O(1)	Direct memory calculation
Append (end)	O(1) amortized	Occasional O(n) resize
Insert at index	O(n)	Shifts right elements
Remove last	O(1) amortized	`pop()`
Remove at index	O(n)	Shifts left elements
Search (unsorted)	O(n)	Linear scan
Search (sorted)	O(log n)	Binary search via `bisect`
Slice	O(k)	k = slice length