a row of lockers, or a treasure hunt

memory is a wall of gym lockers. each one has an address and holds one thing. store something and you get a locker. store more and you need more lockers.

say you're building a grocery list app. there are two basic ways to keep the list: lockers in a row, or a treasure hunt. it helps to know Big O for this one.

#arrays: lockers in a row

an array keeps every item side by side. eggs in locker 3, milk in 4, bread in 5.

that's great until you add a fourth item and locker 6 is taken. now you need four free lockers in a row somewhere else, and everything moves there. you can ask for more lockers than you need up front, but the spare ones sit empty, and once they fill up you're moving again.

#linked lists: a treasure hunt

a linked list lets items sit anywhere. each one holds the address of the next, like a note saying where to look. adding an item never moves the others: put it in any free locker and point the last item at it.

the catch is reading. you know where the first item is, and that's all. to get to the last one, you open the first to find the second, the second to find the third, and so on. you can't skip to the end of a treasure hunt.

an array can. its items are in a row, so item 3 is 3 lockers after the first one. that's also why indexes start at 0: the first item is 0 lockers from the start.

const list = [10, 20, 30, 40];
console.log(list[1]); // 20
console.log(list[0]); // 10
console.log(list[3]); // 40

jumping straight to an item is random access. going one by one from the start is sequential access, and it's the only kind a linked list has.

#inserting in the middle

now keep the list in alphabetical order. butter goes between bread and eggs.

in an array, everything after bread shifts one locker over to make room, and if the row is full, it all moves to a new one. in a linked list, bread points to butter and butter points to eggs. two notes change, nothing moves.

deleting is the same in reverse: the array shifts everything after the gap back, the linked list changes one note.

#the race the array should have lost

there's a catch in that table. inserting into a linked list is O(1) once you're at the right spot, but getting there is a treasure hunt: O(n).

so I timed it. insert random numbers one at a time, keeping the list sorted, walking from the start to find each one's place:

function insertSorted(list, value) {
  let i = 0;
  while (i < list.length && list[i] < value) i++;
  list.splice(i, 0, value);
}
 
function insertSortedLinked(head, value) {
  const node = { value, next: null };
  if (!head || head.value >= value) {
    node.next = head;
    return node;
  }
  let at = head;
  while (at.next && at.next.value < value) at = at.next;
  node.next = at.next;
  at.next = node;
  return head;
}

with 50,000 numbers, the array took 0.84s and the linked list 3.8s (best of 5 runs, Node 24, a Ryzen 7 3700X). the array shifts half its items on every insert and still won by 4.5x.

both walk the same distance. the difference is where they walk: lockers in a row are what a CPU reads fastest, and a linked list sends it to a new address at every step.

that's why arrays are the default, and linked lists mostly show up inside other things: queues, stacks, the chains in a hash table.