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]

Remove a node by changing the preceding link to its successor; deleting the head instead changes the external head pointer. A traversal retaining the last kept node can remove consecutive rejected nodes without advancing that predecessor. When every node is rejected, the head becomes the empty-list pointer.

After a successful search in a linked list, detach the found linked list node and insert that same linked list node at the front. An immediate repetition of that search then succeeds after one key comparison. This helps workloads with temporal locality, though it need not reduce the cost of the search that triggers the move.

A dummy header node lets a search return the found node's predecessor. If that predecessor is already the header, do nothing; otherwise bypass the found node, point it at the old first real node, and point the header at it. This preserves each key/value binding and avoids allocation. It preserves a dictionary abstraction whose ordering is unobservable, but generally changes the abstraction of an ordered list.

A sentinel is a permanently present linked list node that is excluded from the represented data. A header sentinel provides a predecessor even for the first real element, allowing uniform link updates. Its datum has no abstract meaning and must not be counted by the abstraction function. A representation invariant should keep the sentinel outside its own finite acyclic successor chain.

A linked list whose nodes store predecessor and successor references satisfying reciprocal-link consistency. A known node can be unlinked in constant pointer work without searching for its predecessor. The representation uses extra references and requires both directions to be updated on insertion and deletion.

Keep the physical doubly linked list unchanged and represent the logical sequence in either forward or backward order according to a Boolean flag. Toggling the flag reverses the logical contents in constant time complexity. Endpoint insertion and indexed access must interpret their positions using the flag, and the abstraction function explicitly accounts for this choice.

A linked list in which each node stores a successor reference. Forward traversal is direct, but finding a predecessor generally requires a scan unless it is retained separately. A head and tail together with a cached length support constant-time FIFO queue operations.

Scan a nonempty linked list while remembering the predecessor of its least-valued node. A sentinel node supplies a predecessor even when the minimum is the first data node. Once the scan ends, bypass the selected node and detach its outgoing link. Using strict comparison retains the first occurrence among tied minima. Repeated extraction and tail-appending gives stable selection sort without replacing the data nodes or collapsing equal values.

Reverse a finite acyclic linked list using a reversed-prefix head and an untouched-suffix head. Save the suffix head's old successor, redirect its successor to the prefix, then advance both heads. If $P$ and $Q$ are the current sequences of node identities and $S$ the original sequence, the loop invariant is $reverse(P)++Q=S$, with the two reachable node sets disjoint and all payload fields unchanged. Moving $q$ from $Q=q:Q^{\prime }$ to $q:P$ preserves this equation. The suffix length decreases, and at exit the prefix is exactly the reversed original list. The method takes linear running time and constant auxiliary space, reusing the original nodes.

A linked list in which following successors returns to the starting node rather than reaching null. A common non-dummy representation uses a null tail pointer for the empty case and a finite simple cycle for the nonempty case; tail.next is the first node. A traversal stops after one complete turn, comparing object identity with its remembered start. Appending is constant-time once the insertion point and absence of duplicate keys are established.

A linked list whose final node has a null successor, with a null head denoting emptiness. A finite acyclic representation supports a traversal that repeatedly follows next until null. A circular linked list needs a different stopping rule because its final successor points back into the list.

One record holding an item and the references that connect it into a linked list. In the singly linked examples, its next identifies the successor or is null. A linked list node's position in the sequence can change when links change, without moving the linked list node in computer memory.

// Target: computer-science.bigb

A permanent dummy node marking a list boundary, often also storing metadata. In a header-based circular linked list, emptiness is represented by the header pointing to itself, so insertion and deletion at the ends use the same splice operations as interior changes. The header payload need not denote an ordinary data entry.

A linked list whose links are held in ML reference type cells and may be changed. Deleting a node updates the link that reaches it, including the root link when the head is removed. Aliases of links observe these mutations; no fresh list spine is needed for destructive filtering.

// Destination: computer-science.bigb

A linked list whose future structure is obtained by calling a delayed computation. In Standard ML, unit -> node delays a computation until demand. Filtering may need to force arbitrarily many rejected elements to produce its next retained element; filtering an infinite list need not produce a result. Delay alone does not imply memoization.

// Destination: computer-science.bigb

A proper lazy list has a spine exposing either finitely many cons constructors followed by [], or infinitely many cons constructors, without an undefined tail at a finite position. This is a condition on the spine: an element may itself be the bottom value without hiding the list's constructors. A partial list with a finite visible prefix followed by $\perp$ fails this condition. The distinction supports productivity proofs that inspect constructors without evaluating the stored elements.

A generic correct scan cannot always terminate with a certificate that a value is absent from an arbitrary infinite list. Any terminating scan observes only finitely many elements. Changing the unobserved tail to include the value preserves all its observations but invalidates the certificate. The same argument prevents certifying that no occurrence follows the last one already found. A promise such as strict ascending order can provide an independent stopping rule. This explains why mathematical occurrence sets and computed occurrence-position representations of a sequence need different treatment on infinite inputs.

A stream computation is productive when every demanded finite prefix of its output can be produced in finite work. Filtering an infinite list need not be productive: asking for odd elements of [0,2..] never produces even an empty-list constructor. Lazy evaluation alone does not prove productivity.

A list whose spine or elements may contain bottom values. The displayed value has a known finite spine prefix and an undefined tail. An entirely undefined list exposes no outer constructor, while [] exposes a terminating empty list. These distinctions matter to strict functions and to the fold factorisation criterion.

No generic sequential pure Haskell operation can guarantee emission of every available input occurrence when either of two input spines may be the bottom value. To obtain an arbitrary element, it must eventually demand one input. That input can be undefined while the other is a defined singleton, so the demand blocks the promised singleton output. Choosing the other input first reverses the counterexample. Lazy evaluation cannot determine which computation will diverge; the positive two-stream fairness result needs proper lazy lists or a stronger concurrent computational model.

A finite list prefix followed by bottom records only the constructors known so far. The chain $\perp ,x_1:\perp ,x_1:x_2:\perp ,\dots$ approximates an infinite lazy list. A Scott continuous map is determined on the limit by its values on these approximations. This justifies extending an identity proved on finite partial lists to definable operations on infinite lists; equality merely on finite terminating lists does not provide the same premise.