Linked list

A data structure representing a sequence through linked list nodes and links between them. In the singly linked representation used here, each linked list node holds an item and a next reference to its successor. head identifies the first linked list node; the final next is null, meaning no successor. An empty linked list has head = null. Sedgewick and Wayne use this representation to implement both a stack and a FIFO queue. ^[ref]

For $A\to B\to C$, place the linked list nodes at conceptual computer memory positions $40,12,76$, respectively. These deliberately separated labels describe a toy layout, not actual pointer values. The sequence order comes from the links, not increasing positions. To read index $2$, begin at head and follow two next references. For index $i$, this takes $i$ link-following steps and $O(1+i)$ time complexity, hence $O(n)$ in the worst case for $n$ linked list nodes, under the constant-cost operations assumed for the array example. ^[ref]

Suppose a reference to the existing linked list node $B$ is already known. To insert a fresh linked list node $X$ after it, first set X.next = B.next, preserving the old successor $C$, and then set B.next = X. The result is $A\to B\to X\to C$; none of the old items moves. Reversing these assignments would read the newly changed B.next and set X.next = X, losing the route to $C$ from head. This is a two-update algorithm correctness argument, rather than a claim that finding the insertion location is free.

The two pointer updates take $O(1)$ time in Big O notation. The complete insertion has $O(1)$ time complexity if the predecessor is already known, allocating and initializing the fixed-size linked list node costs $O(1)$, and copying its item has constant cost. Finding $B$ from head can instead cost $O(n)$; a position described only by an index does not confer the constant-cost advantage. This makes a linked list useful when an algorithm already holds the needed linked list node, or repeatedly works at the front as a stack does.

Deletion similarly needs the incoming link: to remove $X$ after known $B$, set B.next = X.next. A reference to $X$ alone does not identify its predecessor in this singly linked representation. The head is a special case: after checking for a nonempty linked list, remove it with head = head.next. If a tail reference is also maintained, deleting the only linked list node must clear that reference too; a stored length must also be updated. Removing a linked list node from the sequence and reclaiming its storage are separate responsibilities. ^[ref]

There are practical costs beyond Big O notation. Each singly linked linked list node needs a successor reference in addition to its item; separate allocation may add further overhead, while an array can reserve unused capacity. Consecutive array slots can make a scan reuse nearby contents already brought into a memory cache; separated linked list nodes can make link following wait for successive computer memory fetches. These are layout-dependent effects, not a guarantee that every array operation beats every linked list operation on every machine. An array of references can still lead to scattered objects, and linked list nodes can be allocated close together. ^[ref]