MEPX
Chapter 2 of 10All chapters
  1. 1Why structure matters
  2. 2Arrays and lists
  3. 3Stacks and queues
  4. 4Hash maps and sets
  5. 5Trees
  6. 6Graphs
  7. 7Sorting and searching
  8. 8Recursion
  9. 9Algorithm strategies
  10. 10In practice

Chapter 2 of 10

Arrays and lists

The two sequences.

Arrays

An array holds items in one block, so reading by index is constant time. Inserting in the middle means shifting everything after it, and growing means allocating a bigger block and copying.

  • Appending to a dynamic array is constant time amortised, thanks to doubling.
  • Indexing and iteration are both fast, which covers most everyday code.

Linked lists

Each node points at the next, so inserting or removing at a known point costs nothing. Reaching item n means walking n links, and every node is a separate allocation.