Linked Lists

A linked list stores each item in a small object called a node holding a value and a pointer to the next node. Nodes can live anywhere in memory; the pointers chain them together. You keep a reference to the first node, the head.

Inserting at the front is O(1): make a new node that points at the old head. But reaching the 5th item means walking past four nodes, so access by position is O(n). Lists suit many insertions and deletions; arrays suit fast access by index.