Doubly Linked List Implementation: Two Pointers Are Better Than One

You've seen singly linked lists. Each node knows where to go next. Fine for plenty of things. But the moment you need to delete a node you're already pointing at, or build an LRU cache, you hit a wall. A wall made entirely of O(n) traversal and bad life choices.

A doubly linked list fixes this by giving every node a memory of where it came from. One extra pointer, eight bytes on a 64-bit machine, is what separates a data structure that can't handle LRU cache from one that can. Here's the implementation, the patterns, and where it shows up in interviews.

What a Node Actually Looks Like

Three fields: a value, a next pointer, and a prev pointer.

class Node:
    def __init__(self, val: int):
        self.val = val
        self.next: "Node | None" = None
        self.prev: "Node | None" = None

That prev pointer is not decoration. It lets you delete any node you have a reference to in O(1) time, no traversal required. With a singly linked list, deleting a node means first finding its predecessor, which costs O(n). With a doubly linked list, the predecessor is already wired in. It just sits there, patiently knowing where it came from.

This is why singly vs doubly linked list comparisons always come back to deletion. Everything else is basically the same. This one operation is fundamentally different.

Eight Bytes That Change Everything

One additional pointer per node: 8 bytes on any 64-bit system. A million nodes costs 8 MB you didn't pay with a singly linked list.

Asymptotically, both are O(n) space. But the constant matters at scale. This is why C++ has both std::forward_list (singly linked, minimal overhead) and std::list (doubly linked, full bidirectional traversal). The standard library designers thought the distinction was worth two separate types. These are people who argue about semicolons for a living, so you know they meant it.

Use a doubly linked list when you need O(1) deletion or bidirectional traversal. Otherwise a singly linked list or even an array may be more appropriate. Arrays win on cache performance; linked lists win when you need O(1) arbitrary insertion and deletion. The array vs linked list tradeoff is its own conversation.

The prev pointer is supposed to be a convenience, not a liability. Clean up after yourself.

Sentinel Node Implementation: Eliminate Every Edge Case

Raw doubly linked lists have a nasty problem. Inserting at the head, deleting the last element, and handling an empty list all require special-cased logic. You end up with if-statements scattered across every operation like a game of whack-a-mole where every mole is a null pointer dereference.

The fix is sentinel nodes. A dummy head and a dummy tail anchor the list. They never hold real data.

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

Real nodes always live between two sentinels. Every insert and every delete becomes exactly four pointer reassignments, no special cases, no boundary checks.

def insert_after(self, node: Node, new_node: Node) -> None:
    new_node.prev = node
    new_node.next = node.next
    node.next.prev = new_node
    node.next = new_node

def remove(self, node: Node) -> None:
    node.prev.next = node.next
    node.next.prev = node.prev

insert_after does four assignments. remove does two. The node's own pointers become garbage after removal, and you don't need to clear them. Once you internalize this pattern, you'll use it reflexively in every DLL interview problem.

What Each Operation Actually Costs

Operation	Time	Notes
Insert at head or tail	O(1)	Insert after self.head or before self.tail
Insert before/after a known node	O(1)	Requires a direct reference to the node
Delete a known node	O(1)	Requires a direct reference to the node
Search by value	O(n)	Must traverse from one end
Access by index	O(n)	No random access, no pointer arithmetic

The "requires a direct reference" qualifier matters. A doubly linked list does not make search faster. The O(1) operations only apply when you already have a pointer to the node. This is why DLL almost always pairs with a hash map in interview problems: the hash map gives you the pointer in O(1), the DLL gives you the manipulation in O(1). Neither data structure is complete without the other.

Where This Shows Up in Interviews

LRU Cache

LeetCode 146 is the canonical DLL problem. The requirement is O(1) get and O(1) put, where put evicts the least recently used entry when capacity is exceeded.

The solution: a hash map plus a doubly linked list ordered by recency. Most recently used lives near the head, least recently used near the tail.

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: dict[int, Node] = {}
        self.head = Node(0)
        self.tail = Node(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(value)
        node.key = key
        self.cache[key] = node
        self._insert_front(node)
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

The prev pointer is load-bearing here: without it, moving a node to the front requires O(n) traversal to find its predecessor before unlinking. The full deep-dive is in LRU Cache Implementation.

LFU Cache

LeetCode 460 extends this. Eviction is based on access frequency, with ties broken by recency. The solution uses multiple doubly linked lists, one per frequency bucket. When a node's frequency increases, it moves from one DLL to the next. Same O(1) operations, more bookkeeping.

Python's collections.deque

collections.deque is a doubly linked list of fixed-size blocks under the hood (the blocks are for cache efficiency). appendleft and popleft are O(1) because of the bidirectional pointers. A plain Python list does the same operations in O(n), shifting elements on every call. If you've ever wondered why people make a fuss about deque for queues, this is why.

The Recognition Signal

When you see any of these in a problem statement, reach for DLL plus hash map:

• "O(1) insert and delete from an ordered structure"
• "least recently used" or "least frequently used"
• "eviction policy"
• "move to front" or "move to end"
• Any cache problem where order matters

The pattern is always the same: the hash map solves the lookup problem, the doubly linked list solves the reordering problem. Neither alone handles both. Together, all four operations are O(1).

For more problems using this pattern, Linked List Interview Questions covers the full range from pointer manipulation basics to the harder cache problems.

Where Candidates Actually Fumble

The implementation looks clean on paper. Under interview pressure with someone watching, most people fumble the pointer order in insert_after. The sequence matters: wire new_node before you overwrite node.next, or you lose the reference to the node that was previously next.

You know the implementation. You've coded it before. And then someone is watching you, the cursor is blinking, and your brain decides right now is a great time to forget which pointer goes first.

You nail the O(1) doubly linked list. The interviewer asks if you can also handle concurrent access.

This is what separates candidates who've drilled the pattern from those who understand it conceptually but haven't built it enough times. If you want to practice implementing DLLs in a timed, realistic setting, SpaceComplexity runs voice-based mock interviews where you code live and get rubric-based feedback on exactly this kind of implementation fluency.

Further Reading

• Doubly Linked List (Wikipedia)
• LeetCode 146: LRU Cache
• LeetCode 460: LFU Cache
• std::list (cppreference)
• Doubly Linked List (GeeksforGeeks)