DSA Linked Structures

Types of Linked Lists

An LRU cache designer needs Θ(1) move-to-front when a key is already known. A singly linked list forces a scan for the predecessor; a doubly linked list with a hash map of node handles does not.

A list “type” is a contract about stored links, boundaries, and which mutations a node handle alone can perform: , , , and optional or layouts.

Decision journey

Direction

Do you need prev, or is forward-only enough?

Boundary

Null terminator vs identity stop on a ring.

Handle power

Can one live node unlink itself in Θ(1)?

Ownership

Wrapper nodes, sentinels, or intrusive hooks?

What actually happens

Naive idea: pick “linked list” from a diagram and reuse a linear null-terminated loop everywhere. On a valid ring that loop never terminates. On a doubly list, updating only next leaves prev stale.

Better idea: choose topology from the mutation you repeat. Stacks and simple queues favor plus optional tail. LRU and editor history favor . Round-robin schedulers often want . A collapses edge cases without changing Big-O search.

The improved design still fails when you need random indexing (prefer an array), when an object outlives membership rules, or when stop tests use payload equality on a ring with duplicates.

Invariant (topology contract)

The stored links and stop condition match the chosen type: linear singly ends at null; doubly keeps prev/next inverses; circular returns to the start after exactly n steps; sentinels are structural and never confuse user traversal.

How to choose a list type

1. Do removals start from a known node? Yes → doubly (or intrusive). No → singly may suffice if you already hold the predecessor.

2. Is null a useful end marker? Linear lists yes. Rings need identity or count.

3. Who owns storage? Wrapper nodes are simple; intrusive and index-based lists win when allocation and lifetime are under your control.

Quantitative check

Doubling links roughly doubles reference storage per node (plus headers/padding). On n = 10⁶ nodes, that can be tens of megabytes before payload. The payoff is Θ(1) unlink from a handle: an LRU with q = 10⁶ hits avoids Θ(n) predecessor scans that a singly linked design would pay.

Singly node

1 link

Doubly node

2 links

Linear boundary

null

Circular boundary

identity

See the topology before writing the loop

Switch the stored links and traverse in a legal direction. Notice that a circular list is not an “infinite list”: it is a finite set of nodes whose traversal needs an identity- or count-based stop condition.

Topology explorer

Follow the links, and name the stopping rule

The same payload can have different link fields and boundary contracts. Switch representations, then inspect which references replace null.

Representation

Traversal direction

A singly linked node has no prev link.

fields: value + nextstart: head

Boundary condition

tail.next is null

One traversal

A → B → C → D → null

stop when the cursor becomes null

Good fit

forward scans and minimal link overhead

The four core topologies

Singly linked, linear

value · next

head identifies the first node; each next advances once; the final node has next = null. It minimizes link storage and is ideal when algorithms consume nodes only forward. A tail reference makes append O(1), but it does not reveal the tail's predecessor, so removing the final node still needs a scan.

Invariant: following next from head reaches every live node exactly once, then null.

Doubly linked, linear

prev · value · next

Every adjacent pair records both directions. With head and tail references, the ends have head.prev = null and tail.next = null. Given a live node handle, unlinking it is O(1) because both neighbors are available; finding a value or index remains O(n).

Invariant: for every edge u.next = v, v.prev = u, and conversely.

Circular singly linked

tail.next = head

The last next-link closes the ring instead of storing null. Keeping only tail is often elegant: for a non-empty ring, head = tail.next, so prepend, append, and rotate-to-next are O(1). A singleton must point to itself. Removing a particular node still needs its predecessor.

Invariant: after exactly n next-steps from any node, the cursor returns to that same node.

Circular doubly linked

next ring + prev ring

Both ends wrap: tail.next = head and head.prev = tail. It supports O(1) splicing around a known node in either direction. Implementations commonly add one sentinel node, turning empty, one-node, head, and tail mutations into the same local rewiring pattern.

Invariant: next and prev are inverse permutations over the same finite node set.

Traversal is a termination contract

Reusing a linear while current is not None loop on a valid ring never terminates. Conversely, using “stop at head” on a corrupt ring can also run forever. Choose a contract that matches the representation; in defensive code, a trusted size bound or visited set can detect corruption.

Python

python

1def traverse_linear(head):
2    current = head
3    while current is not None:       # null is the boundary
4        yield current.value
5        current = current.next
6
7
8def traverse_ring_once(head):
9    if head is None:                 # chosen empty representation
10        return
11
12    current = head
13    while True:                      # body must run for a singleton
14        yield current.value
15        current = current.next
16        if current is head:          # identity, not value equality
17            break
18
19
20def traverse_ring_bounded(head, size):
21    current = head
22    for _ in range(size):            # useful when size is a trusted invariant
23        assert current is not None
24        yield current.value
25        current = current.next
26    assert current is head           # catches a broken ring early

Java

java

1import java.util.Iterator;
2import java.util.NoSuchElementException;
3
4final class ListTraversals {
5    static final class Node<T> {
6        final T value;
7        Node<T> next;
8
9        Node(T value) { this.value = value; }
10    }
11
12    static <T> Iterable<T> traverseLinear(Node<T> head) {
13        return () -> new Iterator<T>() {
14            private Node<T> current = head;
15
16            public boolean hasNext() { return current != null; }
17            public T next() {
18                if (!hasNext()) throw new NoSuchElementException();
19                T value = current.value;
20                current = current.next;
21                return value;
22            }
23        };
24    }
25
26    static <T> Iterable<T> traverseRingOnce(Node<T> head) {
27        return () -> new Iterator<T>() {
28            private Node<T> current = head;
29            private boolean started;
30
31            public boolean hasNext() {
32                return current != null && (!started || current != head);
33            }
34            public T next() {
35                if (!hasNext()) throw new NoSuchElementException();
36                T value = current.value;
37                current = current.next;
38                started = true;
39                return value;
40            }
41        };
42    }
43
44    static <T> Iterable<T> traverseRingBounded(Node<T> head, int size) {
45        if (size < 0) throw new IllegalArgumentException("negative size");
46        return () -> new Iterator<T>() {
47            private Node<T> current = head;
48            private int remaining = size;
49
50            public boolean hasNext() { return remaining > 0; }
51            public T next() {
52                if (!hasNext()) throw new NoSuchElementException();
53                if (current == null) throw new IllegalStateException("broken ring");
54                T value = current.value;
55                current = current.next;
56                remaining--;
57                if (remaining == 0 && current != head) {
58                    throw new IllegalStateException("size disagrees with ring");
59                }
60                return value;
61            }
62        };
63    }
64}

Empty

Often head = null, or a sentinel whose links point to itself.

Singleton ring

node.next is node; in a doubly ring, node.prev is node too.

Identity matters

Duplicate payload values are legal, so values cannot identify a completed lap.

Sentinel and header nodes remove boundary branches

A sentinel is a structural node that is never a logical element. A “header node” sometimes means the same thing, but it may also store metadata such as size; document the convention. In a circular doubly linked list, one sentinel can stand in for both boundaries:

A linear singly linked list can instead use a dummy head whose next is the first logical node. That removes the special case for insertion or deletion at index zero, although the chain still ends at null and a separate tail reference may still be useful.

One invariant, including empty

• Empty: S.next = S.prev = S.
• First logical node: S.next.
• Last logical node: S.prev.
• Traversal stops when the cursor is S.
• Insert and erase always operate between two real references, never null.

Python

python

def insert_between(left, node, right):
    # Pre: left.next is right and right.prev is left
    node.prev = left
    node.next = right
    left.next = node
    right.prev = node


def erase(node):
    # Pre: node is linked and is not the sentinel
    left, right = node.prev, node.next
    left.next = right
    right.prev = left
    node.prev = node.next = None  # mark detached


# append: insert_between(S.prev, new_node, S)
# prepend: insert_between(S, new_node, S.next)

Java

java

final class CircularDoublyLinked {
    static final class Node<T> {
        final T value;
        Node<T> previous;
        Node<T> next;

        Node(T value) { this.value = value; }
    }

    static <T> void insertBetween(Node<T> left, Node<T> node, Node<T> right) {
        // Pre: left.next == right and right.previous == left
        node.previous = left;
        node.next = right;
        left.next = node;
        right.previous = node;
    }

    static <T> void erase(Node<T> node) {
        // Pre: node is linked and is not the sentinel
        Node<T> left = node.previous;
        Node<T> right = node.next;
        left.next = right;
        right.previous = left;
        node.previous = null;
        node.next = null; // mark detached
    }

    // append: insertBetween(sentinel.previous, newNode, sentinel)
    // prepend: insertBetween(sentinel, newNode, sentinel.next)
}

A sentinel saves conditional branches, not asymptotic time. It costs one extra node per list and APIs must prevent clients from treating its payload as data or erasing it.

Memory cost: count links, then account for reality

Singly

n × (D + P)

Payload D plus one pointer P per node, before allocator and object overhead.

Doubly

n × (D + 2P)

One additional pointer per node buys direct predecessor access.

Container state

head + tail + size?

Optional references and counters trade a few words per list for cheaper common operations.

These are structural formulas, not exact object sizes. Alignment padding, runtime object headers, allocator metadata, ownership pointers, and per-node allocation granularity can exceed the link fields themselves. Circularity usually changes pointer values, not the number of fields. Compared with a contiguous array, separately allocated nodes also sacrifice spatial locality and may trigger more cache misses.

Operation trade-offs

“Linked-list deletion is O(1)” is only true when the API already supplies every link needed for the splice. Searching for the node, or for its predecessor in a singly linked list: is still linear.

Operation / assumption	Singly	Doubly	Circular singly	Circular doubly
Follow next / full scan	Θ(1) / Θ(n)	Θ(1) / Θ(n)	Θ(1) / Θ(n)	Θ(1) / Θ(n)
Follow prev	Not stored	Θ(1)	Not stored	Θ(1)
Insert after a known node	Θ(1)	Θ(1)	Θ(1)	Θ(1)
Insert before a known node	Θ(i) to find predecessor; worst Θ(n)	Θ(1)	Θ(i) to find predecessor; worst Θ(n)	Θ(1)
Remove a known node	Θ(i) to find predecessor; worst Θ(n)	Θ(1)	Θ(i) to find predecessor; worst Θ(n)	Θ(1)
Pop back with a tail handle	Θ(n)	Θ(1)	Θ(n)	Θ(1)
Detect end of one traversal	cursor is null	cursor is null	cursor returns to start	cursor returns to start

Assumes head and tail are stored where useful. Circularity changes boundary behavior, not the Θ(n) cost of locating an arbitrary value or index.

Specialized representations

Intrusive lists

Link fields live inside the payload object instead of a separately allocated wrapper node. This can avoid allocation, improve control over layout, and allow O(1) removal when the object is in hand: useful in kernels, allocators, and embedded systems. The cost is tight coupling: the object's lifetime must outlive membership, and one pair of link fields usually supports membership in only one list. Multiple memberships require distinct “hook” fields and careful ownership rules.

Unrolled linked lists

Each node stores a small contiguous block of values plus a link to the next block. Fewer pointers and denser scans improve cache locality, while inserts shift within a block and occasionally split or merge blocks. If a balancing rule keeps blocks a constant fraction full, locating a position takes O(n/B) block hops without an index, and local insertion may move O(B) values. Without that occupancy invariant, a chain of nearly empty blocks can still require O(n) hops. B-trees, ropes, and tiered vectors develop this blocking idea further.

XOR linked lists: a historical niche

A node stores address(prev) XOR address(next) in one machine word; traversal reconstructs the missing address using the previous address. It is not a portable substitute for a doubly linked list: moving garbage collectors, memory-safe languages, pointer provenance rules, debugging tools, and concurrent mutation all make it fragile. Use it only in a tightly controlled low-level environment with a measured need.

Multiple and skip links

Nodes can hold child, random, level, or ownership links, but the structure then has more than a simple list invariant. Skip lists add probabilistic forward levels for expected O(log n) search. Multilevel lists need an explicit traversal order and cycle policy. Name each edge's meaning instead of calling every pointer “next.”

Choose from the workload, not the diagram

Dominant need	Usually choose	Reason
Forward-only stack, queue, bucket chain	Singly; add a tail for queue/append	One link per node; a tail makes enqueue or append Θ(1)
LRU cache, editor history, deque internals	Doubly + head and tail	Fast removal and movement when a node handle is already known
Fair scheduler or repeating turn order	Circular singly + tail	head is tail.next; rotation and append are O(1)
Frequent cyclic splicing in either direction	Circular doubly + sentinel	No null boundary cases; predecessor and successor are explicit
Allocator, kernel, or embedded object already owns storage	Intrusive list	Avoids wrapper allocation, but couples membership to object lifetime
Large sequence where cache misses dominate	Unrolled list / block list	Amortizes pointers across several values and improves locality
Fast random indexing is the main operation	Usually not a linked list	A dynamic array, tree, or indexed skip structure matches the access pattern

Mutation bugs are broken invariants

Lost suffix

Overwriting current.next before saving it can make the remaining chain unreachable.

Half-updated pair

Changing u.next without restoring v.prev breaks a doubly linked structure.

Stale boundary

Removing the first or last node must update head, tail, or sentinel links.

Wrong stop test

A ring needs identity or a trusted count; payload equality fails with duplicates.

A reliable splice workflow

State the precondition: which nodes are adjacent and which handles are valid?
Save every neighbor reference that later assignments would overwrite.
Reconnect both sides, then update head, tail, size, or sentinel metadata.
Detach removed nodes deliberately so accidental reuse fails visibly.
Test empty, singleton, two-node, head, tail, and middle cases; validate both traversal directions.

Simple rule of thumb

Singly versus doubly decides whether the predecessor is stored or must be discovered.
Linear versus circular decides whether termination uses null or node identity, not whether the data is finite.
Sentinels regularize edge cases; they do not change asymptotic complexity.
O(1) mutation assumes the necessary node handles are already available and the container metadata is maintained.
Representation wins only when it matches the workload; arrays often beat lists for indexing, locality, and memory density.

Exercises

For an LRU hit on a known node, compare unlink cost on vs lists. What extra structure restores Θ(1) with singly links?
Write stop conditions for a linear scan and a scan of length n. Give an input where payload equality stops too early on the ring.
A circular doubly list uses one . Show empty and one-node states as local link diagrams. Why do head/tail branches disappear?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): circular and sentinel list variants.
Linux kernel documentation on intrusive list idioms (list_head style linkages).
Java LinkedList (doubly linked deque) versus singly linked custom queue designs.

Takeaway

List types are topology contracts. Choose links and stop conditions from the mutation you repeat, then keep that invariant on every splice.