Doubly Linked List with Dummy Nodes

Doubly Linked List

I will skip the basic definition here and focus on implementation.

A doubly linked list is useful because we can add or remove nodes in O(1) time when we already have a reference to the target node.

The downside is that we cannot do random access by index like we can with an array.

This data structure is especially useful in write-heavy scenarios.

Why implementation is tricky

Implementing a doubly linked list is harder than it first appears because there are many edge cases.

You need to update:

• the prev pointer
• the next pointer
• the head side
• the tail side

When adding or removing a node, all of these pointers must stay consistent.

Better Approach: Use dummy nodes

Most edge cases come from None handling at the head and tail of the list.

So instead of letting the list start or end with real nodes, we create two dummy nodes:

• a dummy head
• a dummy tail

All operations happen between these two nodes, so the boundary structure never changes.

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


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

Add a node to the front

Now we can implement add_first:

class DoublyLinkedList:
    def add_first(self, node: Node):
        self._insert_between(self.head, node, self.head.next)

    def _insert_between(self, prev, target, next):
        prev.next = target
        target.prev = prev
        target.next = next
        next.prev = target

Remove a node

Next, implement remove:

class DoublyLinkedList:
    def remove(self, node: Node):
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

        node.next = None
        node.prev = None

Move a node to the front

move_to_front becomes simple:

class DoublyLinkedList:
    def move_to_front(self, node: Node):
        self.remove(node)
        self.add_first(node)

Remove the last real node

Finally, implement remove_last:

class DoublyLinkedList:
    def remove_last(self) -> Node:
        if self.head.next == self.tail:
            raise IndexError
        last = self.tail.prev
        self.remove(last)
        return last

Appendix: Use it for an LRU cache

This structure is a natural fit for an LRU cache.

The dictionary gives O(1) access by key, and the doubly linked list gives O(1) updates to recency order.

class LRUCache:
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._nodes = {}
        self._ddl = DoublyLinkedList()

    def get(self, key):
        node = self._nodes.get(key, None)
        if not node:
            return -1
        self._ddl.move_to_front(node)
        return node.value

    def put(self, key: int, value: int):
        node = self._nodes.get(key, None)
        if node:
            node.value = value
            self._ddl.move_to_front(node)
            return
        new_node = Node(key, value)
        self._ddl.add_first(new_node)
        self._nodes[key] = new_node
        if len(self._nodes) > self._capacity:
            last = self._ddl.remove_last()
            del self._nodes[last.key]