Linked lists

Adding a value at the front of a linked list changes two pointers, whether the list holds 4 values or 4 million.

Values that point to the next one

An array keeps its values side by side, which is why the front is expensive to change. A linked list drops that rule. Each value lives in its own small record called a node, and the nodes can sit anywhere in memory. MIT's 6.006 notes describe a node with two fields: the item, and next, a pointer to the following node. The list itself only remembers the first node, called the head. The last node's next is null, which marks the end.

To read the list you start at head and follow next pointers one by one, like following a chain of notes that each say where the next note is hidden. That has a cost. There is no formula for the address of the fourth node, so getting the value at position i means visiting i + 1 nodes. MIT lists get at(i) for a linked list as O(n), where the array managed it in one step.

// one node per value: { value, next }
let head = null;
for (const v of [4, 30, 7, 12]) head = { value: v, next: head };
// walk the list
for (let n = head; n !== null; n = n.next) console.log(n.value); // 12, 7, 30, 4

Changing the list by relinking

The payoff comes when you change the list. To put a new value at the front, make a node whose next is the current head, then point head at the new node. Two pointer changes, and nothing else moves. Deleting the front node is one change: point head at head.next. Compare that with the array, where the same operations moved every value.

In the middle, the work is finding the spot. To insert at position i you walk to the node just before it (i visits), then do the same two pointer changes: new.next = prev.next, then prev.next = new. The order matters. If you set prev.next first, the rest of the list is lost, because nothing points to it any more. In the lab a step is one node visited or one pointer changed, so inserting at position 2 of a 4-node list costs 2 visits plus 2 changes, 4 steps.

When to use one

A linked list is a good fit when most changes happen at a place you already hold a pointer to, such as the front, and you rarely need position i. Queues and stacks can be built from linked lists, and so can the chains inside a hash table in the next unit. There are variants. A doubly linked list gives each node a prev pointer too, so you can walk backwards and delete a node in one step once you have it. Keeping a tail pointer as well as head makes adding at the end cheap.

In everyday JavaScript you rarely write a linked list, because arrays are well optimized and caches in modern processors favour values stored side by side. The idea matters anyway: trees, graphs and many library structures are built from nodes and pointers in exactly this way.