= Linked list
{wiki}
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>. https://algs4.cs.princeton.edu/13stacks/index.php[Sedgewick and Wayne, Algorithms, section 1.3: linked lists]{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. https://opendatastructures.org/ods-java/3_Linked_Lists.html[Pat Morin, Open Data Structures, chapter 3: links versus indexed access]{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.
\Image[/linked-list-insertion-pointer-updates.png]
{title=Insert a <linked list node> by preserving the successor before redirecting the incoming link}
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. https://opendatastructures.org/ods-java/3_1_SLList_Singly_Linked_Li.html[Pat Morin, Open Data Structures, section 3.1: head removal and empty-list bookkeeping]{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. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf[Ulrich Drepper, What Every Programmer Should Know About Memory, sections 3.3 and 6.2: access patterns and cache use]{ref}
Back to article page
