Arrays
DSA · Arrays and Searching
Theory
An array stores elements in contiguous memory, so any element can be read by its index in O(1) time. Python lists are dynamic arrays: they grow automatically by allocating a bigger block and copying when full, which makes append O(1) on average. Inserting or deleting in the middle is O(n) because later elements must shift. Arrays are the foundation of most other structures, including heaps, hash tables and matrices.
Why we use it
Arrays give the fastest possible random access and are cache-friendly, which makes loops over them very fast in practice.
When to use it
Use an array when you need indexed access, iterate in order, or store a fixed or growing list of items. Avoid it when you frequently insert or delete at the front or middle.
How it works
- Create array
- Elements stored side by side, index 0..n-1
- Access by index? Yes: Jump directly: O(1). No: Scan from start: O(n).
- Insert/delete at the end? Yes: O(1) amortised. No: Shift elements: O(n).
- Done
Syntax
Access arr[i] O(1)
Update arr[i] = x O(1)
Append arr.append(x) O(1) amortised
Insert arr.insert(i,x) O(n)
Delete arr.pop(i) O(n) (pop() at end is O(1))
Search x in arr O(n)Example
scores = [72, 88, 95, 61]
print("Third score:", scores[2])
scores.append(79) # add at the end
scores.insert(0, 50) # add at the front (shifts everything)
print("After changes:", scores)
highest = scores[0]
for s in scores:
if s > highest:
highest = s
print("Highest:", highest, "| Average:", round(sum(scores) / len(scores), 1))Key points
- Index access is O(1)
- Inserting or deleting in the middle is O(n)
- Python lists are dynamic arrays
- Prefer appending at the end for speed