The price of the middle
Contiguity gives arrays O(1) indexing, but it also creates their weakness: there are no gaps. To insert into the middle, every item to the right must slide one slot over to make room. To delete from the middle, everything slides back to close the hole.
Insert or delete at index i touches all n − i items after it:
- at the end: 0 shifts, O(1) (this is why
appendandpop()are cheap) - at the front: n shifts, O(n) (this is
insert(0, x)andpop(0)) - in the middle: about n⁄2 shifts, still O(n)
Watch the shifting happen:
Code exercise · python
Run this. `insert_at` makes room by sliding items right, counting each slide. Front insert shifts all 10 items. End insert shifts none.
Code exercise · python
Your turn: implement `delete_at(arr, i)`. Slide every item after position i one slot LEFT (from i toward the end), count the shifts, then remove the now-duplicated last item with `arr.pop()`. Return the shift count.
The array cost table
Memorize this. It is the baseline every other structure gets compared against.
| operation | Python | cost |
|---|---|---|
| read/write by index | a[i] | O(1) |
| append at end | a.append(x) | amortized O(1) |
| pop from end | a.pop() | O(1) |
| insert at front/middle | a.insert(i, x) | O(n) |
| pop from front/middle | a.pop(0) | O(n) |
| search unsorted | x in a | O(n) |
| search sorted | binary search | O(log n) |
Binary search from lesson 1-3 belongs to arrays for a reason: jumping to the middle of the range needs O(1) indexing. Sorted data in a structure with slow indexing loses the trick, as you will see with linked lists in unit 4.
Quiz
You process a work list by repeatedly taking the OLDEST item with `tasks.pop(0)`. The list holds 100,000 tasks. What is the problem?