Doubly and Circular: Pointers Both Ways and in a Loop

"A singly linked list can only look forward. Add a backward pointer and suddenly you can delete where you stand, walk either direction, and stop writing fragile edge-case code."

Singly's Blind Spot

A singly linked node only knows its next. That one-way vision causes real pain: to delete a node, you need its predecessor (so you can rewire prev.next past it) — but a singly list gives you no way back, so you'd have to re-walk from the head to find the predecessor. O(n), just to delete a node you're literally holding.

A doubly linked list gives each node both next and prev. With a reference to the node and the owning list's boundary information, deletion can reconnect neighbors in O(1). Deleting the head or tail must also update the owner's head/tail unless sentinels remove those edge cases. Backward traversal is the other major benefit.

Circular: the End Loops to the Start

A circular linked list points the last node back to the head, which naturally models round-robin traversal. A circular doubly linked list may also point head.prev to the tail. Queues and bounded buffers do not require this representation; arrays and block-based deques are common alternatives.

Doubly linked = each node knows prev and next: bidirectional traversal and O(1) deletion given the node plus owner/boundary handling. Circular = the ends join into a ring, useful for round-robin traversal. The cost is extra pointers and invariants.

The Pro Move: Sentinel Nodes

Real linked-list code is riddled with edge cases: empty list, deleting the head, deleting the tail, a list of one. Each needs a special if, and each if is a place to get it wrong. The classic fix is a sentinel (or "dummy") node — a permanent, value-less node that sits before the real head (and often one after the real tail). Now there is no "head deletion" special case, because every real node always has a real prev. The sentinel costs one node of memory and erases a whole category of bugs. This is exactly how production deques and many standard libraries do it.

Pippa's Confession

My doubly linked list worked perfectly until someone deleted the head, and then it exploded — because head-deletion was the one case my pointer logic didn't cover. Dad introduced a sentinel node and every special case I'd been hand-coding just... vanished. The empty list, the single-element list, head and tail deletion — all became the same uniform code. It taught me that the best way to handle edge cases is often to design them out of existence.

Code

O(1) deletion with a backward pointer·python

class DNode:
    """A doubly linked node: value plus pointers both ways."""
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

def delete(node):
    """Unlink a non-boundary node in O(1) when its neighbors are available.
    An owning list must separately update head/tail for boundary deletion."""
    if node.prev:
        node.prev.next = node.next   # neighbor before skips over `node`
    if node.next:
        node.next.prev = node.prev   # neighbor after points back past `node`
    # `node` is now unlinked from both sides; garbage collected if unreferenced.

# Build a <-> b <-> c, then delete b in O(1) using only `b`.
a, b, c = DNode("a"), DNode("b"), DNode("c")
a.next = b; b.prev = a
b.next = c; c.prev = b

delete(b)                 # we only needed b itself, no walk from the head
print(a.next.value)       # 'c' — a now links straight to c
print(c.prev.value)       # 'a' — and c links straight back to a

Exercise

Explain in your own words why deleting a node you hold a reference to is O(1) in a doubly linked list but O(n) in a singly linked list. Then: name a real-world system that suits a CIRCULAR list, and say what 'the end points back to the start' buys it.

Hint

Doubly: with the node and owning boundary state, you can rewire neighbors and update head/tail in O(1). Singly: you generally need to find the predecessor first, which is O(n). Circular fits round-robin schedulers / repeat playlists — the loop means 'after the last, naturally back to the first' with no special-case reset.

Singly's Blind Spot

Circular: the End Loops to the Start

The Pro Move: Sentinel Nodes

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0