Prev and Next: How Doubly Linked Lists Make O(1) Deletion Real

You have a node. You want to delete it. In a singly linked list, that node doesn't know who's behind it, so you walk the whole list from the head to find the predecessor. O(n). Every time. It's like asking someone to leave a queue but first making them walk to the back of the line to figure out who they were standing behind.

The doubly linked list fixes this with one extra pointer. Each node carries prev alongside next. That's the whole idea. But that single pointer is why LRU caches, browser history, and undo stacks work the way they do. It's why Python's collections.deque lets you pop from either end in constant time. The asymmetry between singly and doubly linked lists collapses almost entirely to one question: do you ever need to delete a node without walking the list first?

When the answer is yes, reach for the DLL.

What's Actually in Memory

A doubly linked list node holds three things: a data value, a next pointer, and a prev pointer.

Each node pays 16 bytes for its two pointers. Not free, but not much.

On a 64-bit system, the two pointers alone cost 16 bytes per node, on top of whatever the data is. That overhead doubles the pointer cost compared to a singly linked list. In memory-constrained environments it matters.

The nodes themselves are heap-allocated objects scattered through memory with no adjacency guarantee. This is the cache-unfriendly reality of any linked list: CPU cache lines load 64 bytes of contiguous memory, and chasing a pointer to an arbitrary address wastes most of that. Arrays win on cache locality every time. The trade you're making with a DLL is O(1) structural manipulation in exchange for worse sequential access performance.

CPython's collections.deque understands this. Rather than allocating individual nodes, it allocates blocks of 64 elements and chains those blocks as a DLL. You keep O(1) push/pop at both ends, you eliminate realloc(), and you recover most of the cache locality you'd lose with a pure node-per-element design.

The XOR trick (and why you'll never use it)

There's a variant called the XOR linked list. Each node stores prev XOR next instead of two separate pointers. To traverse forward from node B if you came from A: B.both XOR addr(A) gives you C. You halve the pointer storage. It's clever. It's also basically unusable in managed languages where you don't hold raw numeric addresses, and even in C it breaks most garbage collectors. Know it exists. Leave it in the trivia bucket.

The Sentinel Node Trick

A sentinel (or dummy) node is a permanent placeholder that never holds real data. You put one at the head, one at the tail, and link them circularly. An empty list looks like this:

Empty does not mean null. Two sentinels are always standing watch.

Add three nodes and it becomes:

Every real node always has two real neighbors. The sentinels guarantee it.

The sentinels are always there. The list is never empty in the traditional sense because the two dummies are permanent fixtures.

Why this matters: every insert becomes "insert between two existing nodes." There are no edge cases for empty lists, no special logic for inserting at the head, no null checks before accessing node.prev.next. You write one insert function and it handles all positions identically.

The delete function similarly becomes "unlink this node from its two neighbors," and since every real node always has two real neighbors (at minimum the two sentinels), you never have to guard against null on either side.

Without sentinels, you spend half your bug-fixing time on off-by-one errors at the list boundaries. With them, those cases don't exist.

Core Operations

Complexity table

Why insert is O(1)

Four pointer assignments. That's the whole operation. No searching, no shifting.

Inserting node N after node A (and before B = A.next) requires exactly four pointer writes:

N.prev = A
N.next = B
A.next = N
B.prev = N

The sentinel trick means this same four-line sequence works whether A is the head sentinel, the tail sentinel, or any node in between.

Why delete is O(1), and the Critical Caveat

Two assignments. N is gone. The list didn't have to go looking for it.

To delete node N (sandwiched between A and B):

A.next = N.next    (= B)
B.prev = N.prev    (= A)
[optionally] N.next = N.prev = null

Two assignments. But there is a catch that trips people up in interviews: this O(1) delete only applies when you already hold a pointer to node N. If you only know the value you want to delete, you still need O(n) to find the node. The list doesn't index. It just chains.

This is exactly why the LRU cache combines a DLL with a hashmap: the map gives O(1) lookup by key, which hands you the direct node pointer, which enables O(1) removal from the DLL. Neither data structure alone gives you constant time; together they do.

Why tail operations are O(1) but would be O(n) in a singly linked list

This is the sharpest practical difference. To delete the last node from a singly linked list, you need to update the second-to-last node's next pointer to null. But the last node doesn't carry a prev pointer, so you have to traverse from the head to find the second-to-last node. O(n).

In a DLL, the last node's prev pointer IS the second-to-last node. No traversal. O(1). This is why a doubly linked list can implement a double-ended queue (deque) but a singly linked list cannot do it efficiently.

Doubly Linked List Implementations

class Node:
    def __init__(self, value=None):
        self.value = value
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        self.head = Node()  # sentinel head
        self.tail = Node()  # sentinel tail
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def _insert_between(self, value, before, after):
        node = Node(value)
        node.prev = before
        node.next = after
        before.next = node
        after.prev = node
        self.size += 1
        return node

    def append(self, value):
        return self._insert_between(value, self.tail.prev, self.tail)

    def prepend(self, value):
        return self._insert_between(value, self.head, self.head.next)

    def delete(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None
        self.size -= 1

    def to_list(self):
        result = []
        current = self.head.next
        while current is not self.tail:
            result.append(current.value)
            current = current.next
        return result


# Usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
node_three = dll.append(3)
dll.prepend(0)
print(dll.to_list())   # [0, 1, 2, 3]
dll.delete(node_three)
print(dll.to_list())   # [0, 1, 2]

What Problems It Solves

The DLL is the right tool when you need a data structure that can be efficiently modified from both ends, or when you hold direct references to elements you may need to remove or reposition. Concrete cases:

Caches. Both LRU (Least Recently Used) and LFU (Least Frequently Used) caches require O(1) eviction. LRU evicts the tail of the DLL; LFU groups nodes by frequency in separate DLLs. Without O(1) tail removal, eviction degrades to a scan.

Deques. Double-ended queues need O(1) push and pop at both ends. A DLL with sentinels handles all four operations identically.

Text editors and undo stacks. A cursor in a text buffer is a pointer into a DLL of characters or lines. Inserting and deleting at the cursor position is O(1). Undo moves backward through change history.

Browser history. Forward and back navigation are O(1) pointer moves along the history list. Adding a new page discards the forward list by relinking from the current node.

Operating system internals. Linux uses a circular DLL (list_head) pervasively in the kernel for everything from process scheduling queues to timer lists. The sentinel-free circular design, with nodes embedded directly in larger structs via container_of, keeps overhead near zero.

Recognizing the Pattern

A DLL fits when the problem takes one of two shapes:

1. You need O(1) operations at both ends of a sequence.
2. You need to delete or move a node you already have a reference to, without searching.

Worked example: LRU Cache (LeetCode 146)

Problem: Design a cache that stores key-value pairs with a capacity limit. get(key) returns the value and marks that key as recently used. put(key, value) inserts or updates a key, evicting the least recently used entry if the cache is at capacity. Both operations must run in O(1).

Why DLL fits: You need to maintain a recency order and evict the oldest entry in constant time. An array gives you O(n) delete at an arbitrary position. A heap gives you O(log n) removal. A DLL with sentinel head and tail lets you move any node to the front in O(1) and evict the least recent in O(1). The missing piece is finding the node by key. That's where the hashmap comes in.

The hashmap hands you the pointer. The DLL does the surgery. Neither works alone.

HashMap:  { A -> NodeA, B -> NodeB, C -> NodeC }
               ↓          ↓          ↓
DLL: HEAD <-> [C] <-> [A] <-> [B] <-> TAIL
              MRU                      LRU

Access key A: NodeA moves to front.

DLL: HEAD <-> [A] <-> [C] <-> [B] <-> TAIL

Cache full, insert D: evict B (tail neighbor), insert D at front.

DLL: HEAD <-> [D] <-> [A] <-> [C] <-> TAIL

Worked example: Browser History (LeetCode 1472)

Problem: Implement a browser history. visit(url) visits a new page, clearing any forward history. back(steps) moves back up to steps pages. forward(steps) moves forward up to steps pages.

Why DLL fits: Each page is a node. A cursor tracks your current position. Visiting a new page means inserting a node after the cursor and relinking the tail sentinel directly after the new node, which discards former forward history in one pointer write. Moving back or forward is just walking prev or next pointers, clamped at the sentinels.

A simple array-with-index approach works here too, but the DLL makes the intent transparent. You're navigating a chain of pages where each page knows exactly what came before and after it.

Recap

• A doubly linked list adds a prev pointer to each node, enabling O(1) deletion of any node you hold a reference to, and O(1) operations at both ends.
• The critical caveat: O(1) delete requires a direct node pointer. Finding a node by value is still O(n).
• Sentinel (dummy) nodes at head and tail eliminate all null checks and edge cases by making every insert and delete a "between two nodes" operation.
• Every singly linked list operation is also O(1) or O(n) in a DLL, so the DLL strictly extends what a SLL can do. The only cost is the extra prev pointer per node (16 bytes on 64-bit systems for both pointers total).
• The LRU cache is the canonical interview pattern: hashmap for O(1) lookup, DLL for O(1) ordering and eviction.
• CPython's collections.deque uses blocks of 64 elements chained as a DLL to combine O(1) end operations with better cache locality than a pure node DLL.
• Rust makes safe DLL implementations genuinely hard due to ownership rules. std::collections::LinkedList exists but VecDeque is usually preferable.

If you're preparing for system design or DSA interviews, the LRU cache question comes up constantly, and it's almost always a DLL problem in disguise. SpaceComplexity runs voice-based mock interviews that push you to explain the reasoning behind your data structure choices out loud. That's where most candidates lose points. Worth a try before your next loop.

For more on the interview patterns that show up alongside this: Ask These Clarifying Questions First. The Algorithm Will Follow. is a good companion read, and Dynamic Programming Is Just Recursion With a Memory covers another structure where the storage choice determines everything.

Further reading

• Doubly Linked List - GeeksforGeeks, comprehensive walkthrough of operations with diagrams
• Doubly Linked List using Sentinel Nodes - GeeksforGeeks, sentinel pattern in detail
• std::list - cppreference, C++ STL doubly linked list specification
• collections.deque - Python docs, official Python deque documentation
• Rust std::collections::LinkedList, and why the Rust docs themselves suggest you probably want VecDeque instead