Linked lists

An array stores neighbours in neighbouring memory. A linked list stores a node: a value, plus a reference to the next node. The list itself is the reference to the first node, called the head. The last node's next is null.

You cannot jump to the 10th node. You walk from the head, which is O(n). Inserting or rewiring after a node you already hold is O(1), because you change a couple of pointers and nothing else has to slide. That is the whole trade against arrays.

Reversing a list is the exercise that makes the pointers feel real. Keep the previous node, the current node, and the next node you are about to lose. Point current back at previous, then step all three forward. When current runs out, previous is the new head. If you overwrite next before you have saved it, the rest of the list is gone.