The last question of lesson 2's homework asked for a usage pattern where []Item is the wrong structure. Here it is.

The playlist

A user drags a track from position 47 to position 3. Then from 12 to 80. Then again. The library holds 100,000 items.

With a []Item, every one of those moves shifts every element in between. That is O(n), and it happens on every drag.

The structure that never has to shift looks like this:

  ┌──────┐     ┌──────┐     ┌──────┐
  │ Item │ ←→  │ Item │ ←→  │ Item │
  └──────┘     └──────┘     └──────┘

Each node holds its item and two pointers — to the neighbour on its left and the one on its right. The elements no longer sit next to each other in memory. That is exactly why nothing needs shifting: to splice a node in between two others you rewrite four pointers and you are done.

Four — whether the list holds 10 items or 10,000,000. That is O(1).

What you pay for it

Three things, and all three matter:

1. Indexing is gone. lib[47] on an array is one multiply. In a linked list there is no way to compute where node 47 is — you have to walk there from the front, one node at a time. Indexing goes from O(1) to O(n).

2. More memory. Every node adds two pointers — 16 bytes on a 64-bit machine — to every item.

3. Scattered memory. Array elements sit side by side, so the processor fetches them in batches. Nodes are spread all over memory, and every hop can mean another trip to RAM.

That third cost does not show up in a Big-O count. In step 4 it shows up in a measurement.