Arrays
Loading
Loading
Arrays
Why indexing is instant and inserting in the middle is not.
By the end of this chapter
An array stores its elements in one unbroken run of memory. Every element occupies the same number of bytes, which is the property everything else follows from.
Concept
Because the elements are equally sized and adjacent, the machine computes the address of element i as start + i × size. That is one multiplication and one addition, regardless of whether i is 0 or 10,000,000. Nothing is searched.
Contiguity is also the reason inserting into the middle is expensive: there is no gap, so room has to be made by shifting everything after the insertion point.
insert 9 at index 1 of [4, 7, 2, 8][4, 7, 2, 8, _]make room at the end[4, 7, 2, 8, 8]shift 8 right[4, 7, 2, 2, 8]shift 2 right[4, 7, 7, 2, 8]shift 7 right[4, 9, 7, 2, 8]write 9 into the gap[4, 9, 7, 2, 8]| Operation | Time | Space |
|---|---|---|
| Read or write by index | O(1) | O(1) |
| Appendcapacity doubles | O(1) amortised | O(1) |
| Insert or delete at the end | O(1) amortised | O(1) |
| Insert or delete in the middle | O(n) | O(1) |
| Search, unsorted | O(n) | O(1) |
| Search, sorted | O(log n) | O(1) |
Quick quiz
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: take the quiz above.