Singly Linked Lists

The 10-second versionCopy Anchor Link

A linked list is a chain of small nodes scattered wherever memory allows. Each node holds a value and a pointer to the next node; a single head pointer names the start. Because nodes don't have to sit next to each other, you can insert or remove one in O(1) if you already hold the node next to it — no shifting, unlike an array. The price is the exact opposite of the array's strength: there's no address arithmetic, so reaching the i-th element means walking i links, O(n). It's a lever: trade instant indexing for instant splicing.

Why this existedCopy Anchor Link

In the mid-1950s, a group at the RAND Corporation — Allen Newell, Cliff Shaw, and Herbert Simon — set out to write a program that could prove theorems in propositional logic. Their Logic Theory Machine (working in 1955–1956) had to represent expressions, sub-expressions, and the same sub-expression appearing in many places at once. That last part is the killer: if two formulas share a piece, you want to share the piece, not copy it.

Arrays can't do that. A contiguous block is great when the data is flat, fixed, and independent — but symbolic expressions are nested, elastic, and shared. So Newell, Shaw, and Simon built their data out of memory cells with links, using the IPL list-processing language they grew alongside the machine. A "list" wasn't a block; it was a path through scattered cells.

• 1956 — the Logic Theory Machine's ideas are drafted up as list processing in IPL; the node-and-link representation becomes standard.
• 1960 — Lisp turns the idea into a primitive: the cons cell (two fields, value and next) makes linked lists the language's default list type.
• 1972 — C makes the machinery visible: a struct with a pointer to another struct of the same type. Nothing is hidden.
• now — functional languages still build lists out of cons cells, and every OS kernel's free list is a linked structure.

Why it mattered then: list processing made it possible to write programs about symbols and structure rather than arrays of numbers. It's the moment "data structure" started meaning shape you can navigate, and it's the seed of everything from Lisp to garbage collectors to graph adjacency lists.

Inside the inventor's headCopy Anchor Link

Newell's team has a list of unknown length, and its pieces are shared. They try the obvious tool first: an array. It fights back immediately. How big? If two expressions share a sub-list, do you copy it into both? What happens when a formula grows in the middle?

Here's the trap that kills the array for this job — watch what "put something at the front" costs:

// Array: unshift moves every element — Θ(n)const arrayPrepend = (a, x) => { a.unshift(x); return a; };// Linked list: one new node pointing at the old head — Θ(1)const listedPrepend = (head, x) => ({ value: x, next: head });

The aha is that the order of the data and the order of the memory don't have to match. Once each element can say "the next one is over there," the list is free to grow, shrink, and share in any direction, anywhere in the heap. Everything you gain — O(1) prepend, O(1) splice, shared tails — comes from abandoning contiguity, and everything you lose comes from the same place.

The final approachCopy Anchor Link

The shapeCopy Anchor Link

A singly linked list is one pointer into a chain of nodes, each holding a value and a next:

(Each box is one heap-allocated node; the arrows are the next pointers.)

The invariantCopy Anchor Link

• head points at the first node, or is null for an empty list.
• Every node's next points at the next node, or is null at the tail. Following next from head therefore visits every node exactly once and then stops.

That single rule of a terminating chain is what makes traversal, search, and reverse all work: you walk until you fall off the null at the end.

A flow: prepend a valueCopy Anchor Link

A worked trace: prepend 5 to [7 → 3 → 9]Copy Anchor Link

And the reverse, because it's the classic pointer puzzle — walk the chain once, flipping each arrow behind you:

Three pointers — prev, cur, next — are all it takes, in Θ(n) time and Θ(1) extra space. The subtlety is saving next before overwriting cur.next; forget it and you lose the rest of the list.

It in codeCopy Anchor Link

class Node {  constructor(value, next = null) { this.value = value; this.next = next; }}const pushFront = (head, value) => new Node(value, head);const find = (head, target) => {          // Θ(n)  for (let cur = head; cur !== null; cur = cur.next)    if (cur.value === target) return cur;  return null;                            // fell off the end};const reverse = (head) => {               // Θ(n) time, Θ(1) space  let prev = null;  while (head !== null) {    const next = head.next;               // save the rest    head.next = prev;                     // flip the arrow    prev = head;                          // advance prev    head = next;                          // advance head  }  return prev;                            // old tail is the new head};

In Rust, the "rest of the list" is Option<Box<Node>>: the node owns its successor, so the whole chain is a tree of ownership. Dropping the head recursively drops everything — which is also why a very long list needs care when it's freed.

ComplexityCopy Anchor Link

A singly linked list, head-on:

Side by side with the array, which is the whole point of the trade:

That last row deserves a sentence: even when the Big-O is identical, an array usually wins in practice because its elements share cache lines. A linked list pays a possible cache miss — up to ~100× a stack access — on every hop. Big-O hides the constant; the hardware doesn't.

Where you meet it todayCopy Anchor Link

• Graph adjacency lists. Each vertex heads a list of its neighbors — you never know a degree up front, so you link as you go.
• Hash-table chaining. Collisions in a bucket are stored as a short linked list you walk on lookup.
• Free lists. Allocators, thread pools, and OS page managers keep a linked list of available blocks so reuse is O(1).
• Persistent / functional structures. Prepending to a Lisp/Haskell list makes a new list that shares the whole tail with the old one — trivially, because of the links.

// Bucket as an array of linked nodes (key, value, next).const bucket = new Array(64).fill(null);const hash = (key) => key.length;    // toy hash for illustrationfunction lookup(key) {  for (let e = bucket[hash(key) % 64]; e !== null; e = e.next)    if (e.key === key) return e.value;  return undefined;}

RecapCopy Anchor Link

• A linked list is a chain of heap nodes, each holding a value and a next link; head names the start and the tail's next is null.
• Insertion and removal given a node are O(1) — no shifting — because order lives in the links, not in the addresses.
• Access by index is O(n): no arithmetic, so you walk. This is the array's revenge.
• Nodes cost an extra pointer each and are cache-unfriendly — the hidden tax behind the "same Big-O, slower in practice" reality.
• It's the foundation of graph adjacency lists, hash chaining, free lists, and functional persistent lists.

Next up: Doubly & Circular Linked Lists — adding a back-pointer so you can delete a node you hold in O(1), and closing the loop so the last node knows the first.