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 fixes this by giving every node two pointers: next and prev. Now, given any node, you can reach both neighbors instantly — so deleting it is O(1): point node.prev.next at node.next, and node.next.prev back at node.prev. You can also walk the list backward, which singly lists simply can't do.

Circular: the End Loops to the Start

A circular linked list points its last node back at the head (instead of at None), forming a ring. This is perfect for anything that cycles: round-robin scheduling (give each task a turn, forever), a music playlist on repeat, or a fixed-size ring buffer for streaming data. A circular doubly linked list — where head.prev is the tail — is one of the most flexible structures there is, and it's exactly what powers many real queue implementations.

Doubly linked = each node knows prev and next: bidirectional traversal and O(1) deletion given a node. Circular = the ends join into a ring, ideal for round-robin and buffers. The cost is double the pointers and double the bookkeeping per operation.

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):
    """Delete a node given ONLY a handle to it — O(1) in a doubly linked list.
    Singly linked can't do this without an O(n) re-walk to find the predecessor."""
    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: you have prev and next, so you rewire two neighbors instantly. Singly: you'd have to walk from the head to find the predecessor (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