207: Linked Lists: Singly, Doubly, Sentinel Nodes, Reversal, and Pointer Invariants

Learning outcomes

By the end of this lesson, you should be able to:

explain and apply singly linked lists in a realistic implementation;
explain and apply doubly linked lists in a realistic implementation;
explain and apply sentinel nodes in a realistic implementation;
explain and apply reversal in a realistic implementation;
explain and apply fast and slow pointers in a realistic implementation.

Prerequisites and retrieval

This lesson builds on the earlier 01–06 foundation and the preceding lessons in this module. Before you read, retrieve one concrete example from an earlier project in which a similar concern appeared. Perhaps you had to maintain order, remove an item when you already had a reference to it, or reason about two cursors moving through data. The point is not to memorize linked-list terminology. It is to make a defensible choice in an interview-sized problem and in a production data-processing problem, using constraints rather than a memorized template.

Terminology

Singly linked lists: A node stores a reference to the next node, or to no node when it is the end of the list. That definition is more useful than treating the phrase as vocabulary: it tells you which links exist and which operations will require a predecessor.
Doubly linked lists: Prev/next links support O(1) removal when you have a node reference and allow traversal in both directions. The trade-off is extra memory and more pointer updates, which means more invariants can be broken.
Sentinel nodes: Dummy head and tail nodes represent the boundaries of a list without representing actual data. They reduce special cases for an empty list and for boundary insertion or deletion, making the invariants easier to maintain.
Reversal: Iterative reversal rewires links while maintaining previous/current/next pointers. Recursive reversal uses call-stack space and can hit recursion limits on large lists.
Fast and slow pointers: Pointers moving at different speeds solve midpoint, cycle-detection, and nth-from-end problems. The useful skill is stating the distance or invariant being preserved.
Merge and splice: Merging sorted lists can reuse existing nodes in O(n+m) time. That is efficient, but it also raises an ownership question: are the inputs mutated, and may their nodes be shared with callers?

Mental model

Treat Linked Lists: Singly, Doubly, Sentinel Nodes, Reversal, and Pointer Invariants as a design problem with observable inputs, outputs, invariants, and failure modes. A linked list gives up random access in exchange for O(1) local insertion or removal when the relevant node, and sometimes its predecessor, is already known. In interview questions, the real test is usually whether you can preserve pointer invariants; in production, an array or another structure may still be the better choice.

A strong implementation makes its assumptions visible. It defines what an empty list looks like, narrows uncertainty at the boundaries, and leaves evidence—tests, types, constraints, metrics, or diagrams—that makes the safety argument reviewable. A useful sequence for both interviews and production work is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from the requirement straight to a library call or a pointer manipulation. First state what must remain true. Then choose the mechanism that makes those conditions easiest to enforce and inspect.

Deep dive

1. Singly linked lists

The simplest list node points only to the next node. Inserting at the head is O(1), because the new node needs one link to the old head. Reaching the k-th element is O(k), however, because there is no direct index lookup; you must follow each link in order. Deleting a node also usually requires its predecessor so that the predecessor can skip over the removed node.

Decision rule: Use a singly linked list deliberately when its contract or invariant is easier to prove than the alternatives. If the structure merely saves a little typing while hiding an important assumption about access or ownership, choose the more explicit design instead.

2. Doubly linked lists

A doubly linked node has both prev and next links. With a reference to the node, removal can be O(1): connect its predecessor to its successor and update the corresponding reverse links. The same links enable traversal in either direction. The cost is additional memory and additional writes on every insertion, removal, and boundary update.

This is where people usually get confused: O(1) removal assumes that the node reference is already available and valid. Finding that node can still take O(n), and a stale or foreign node reference can corrupt the list unless the ownership contract prevents it.

Decision rule: Use a doubly linked list deliberately when bidirectional traversal or O(1) removal from a known node makes the contract or invariant easier to prove. If the extra link only hides an access assumption, prefer the simpler structure.

3. Sentinel nodes

Boundary conditions are where linked-list code tends to become fragile. A sentinel is a dummy head or tail node that is always present but does not contain a real item. With both sentinels, an empty list can have head.next === tail and tail.prev === head; an ordinary node always sits between two nodes. Insert and delete code can then update neighbors without branching separately for the first item, last item, or empty list.

The sentinel is an implementation aid, not data. Callers should not receive it as a real element, and traversal must stop at the sentinel rather than treating it as a value. This distinction keeps the simpler pointer invariant from leaking into the public API.

Decision rule: Use sentinel nodes deliberately when they reduce boundary cases and make the contract or invariant easier to prove. If they only obscure where real data begins and ends, keep explicit boundary handling instead.

4. Reversal

Reversal changes every next link, so the current node's old successor must be saved before that link is overwritten. The iterative form maintains previous, current, and next pointers: save the successor, point current backward, advance previous, and then advance current. At the end, previous is the new head. Its time complexity is O(n) and its auxiliary space is O(1).

The recursive form can be elegant for a small list, but each node consumes call-stack space. That makes it vulnerable to recursion limits for a large list. For either approach, check the empty list and one-node list explicitly in tests; both should remain valid without special values being introduced.

Decision rule: Use reversal deliberately when it makes the required contract or invariant easier to prove. Prefer the iterative version when input size is unbounded or production reliability matters more than recursive terseness.

5. Fast and slow pointers

Two pointers moving at different speeds let you derive useful relationships without indexing into the list. A slow pointer can move one node at a time while a fast pointer moves two, allowing the slow pointer to reach a midpoint when the fast pointer reaches the end. In a cycle, repeated movement can cause the two pointers to meet. To find the nth node from the end, maintain a fixed gap between a leading pointer and a trailing pointer.

State the distance or invariant instead of memorizing a formula. For example, after advancing the lead pointer by n nodes, keep the lead and trailing pointers n nodes apart while advancing them together. Decide how even-length lists, n === 0, and n larger than the list length are defined before writing the loop.

Decision rule: Use fast and slow pointers deliberately when their preserved distance or speed relationship makes the contract or invariant easy to prove. If the requirement needs random access or repeated arbitrary positions, a different representation may be clearer.

6. Merge and splice

When two lists are sorted, merge them by repeatedly linking the smaller current node to the result. Reusing nodes gives O(n+m) time and avoids allocating a second value for every element. A final remainder can be attached directly once the other input is exhausted.

There is one subtle detail worth knowing: node reuse is a mutation and an ownership decision, not just an optimization. Document whether the inputs are consumed, whether callers may still traverse them, and whether a node can be shared by more than one list. If those conditions are not safe, copy nodes instead and account for the additional O(n+m) space.

Decision rule: Use merge and splice deliberately when node ownership is explicit and the O(n+m) traversal fits the requirement. If callers retain the inputs or sharing is possible, choose copying or another design that preserves the ownership contract.

Worked example

Start with two versions of the requirement in your head: an interview-sized pointer problem and a production data-processing operation. In both cases, write the requirement in one sentence, list the input and output contracts, and identify which concept owns each failure mode. Do not let the presence of a linked list blur system boundaries. Parsing and validation belong at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing those concerns can make a happy-path demo shorter, but it makes pointer and data edge cases much harder to reason about.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

This deliberately small example is not a linked-list implementation. It illustrates the engineering habit that should come first: state what answer means before selecting a representation. Here, after each iteration, answer is the greatest value encountered so far. That invariant also exposes an edge case: returning 0 for an empty input is only correct if the contract defines that result. For arbitrary numbers, including negative values, the contract may need a different empty-input policy.

Walk the example through at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where that situation is relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. That discipline is just as useful when the implementation is pointer-heavy: it separates a broken list invariant from invalid input, a retry policy, or an unavailable dependency. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For linked structures, also ask who owns each node, whether a list can be traversed while it is being mutated, and how a corrupted link will be detected. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after evidence identifies the bottleneck or risk.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. A data structure does not replace those guarantees; it only makes one part of the behavior easier or harder to implement correctly.

Guided lab

Implement list reversal, cycle detection, merge-two-sorted-lists, and remove-Nth-from-end with a sentinel. Before executing the code, draw the pointer states for one tricky edge case, such as an empty list, a one-node list, a cycle, or removing the head. The drawing should show which links change and what each pointer means at that moment.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

Edge cases and failure modes

Singly linked lists: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify that traversal terminates and that deleting the head does not lose the remainder of the list.
Doubly linked lists: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. After each mutation, verify both directions and the boundary links.
Sentinel nodes: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Confirm that sentinels are never returned as data and that an empty list still links its boundaries correctly.
Reversal: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Preserve the old successor before rewiring and verify that no cycle is introduced accidentally.
Fast and slow pointers: Test absence, malformed input, duplicates, ordering or concurrency where applicable, and behavior at the smallest and largest credible sizes. Define the behavior for even lengths, a missing cycle, an invalid n, and a gap that exceeds the list.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pointer pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing list, draw or log the links before and after the mutation, and inspect the actual node identity rather than only its value. Trace the boundary where the invariant first becomes false: a missing predecessor update, a stale sentinel link, an overwritten successor, or a loop that never advances. Then fix the owning layer instead of adding a downstream patch. If the issue involves concurrent mutation, make the synchronization or immutability contract explicit rather than assuming pointer updates are automatically safe.

Interview questions

What problem do singly linked lists solve, and what trade-off or failure mode would make you choose a different approach?
What problem do doubly linked lists solve, and what trade-off or failure mode would make you choose a different approach?
What problem do sentinel nodes solve, and what trade-off or failure mode would make you choose a different approach?
What problem does reversal solve, and what trade-off or failure mode would make you choose a different approach?
What problem do fast and slow pointers solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Linked Lists: Singly, Doubly, Sentinel Nodes, Reversal, and Pointer Invariants to another developer in five minutes. Include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. If you cannot state what every pointer means before and after a mutation, the implementation is not ready to trust.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.