Doubly Linked List

A doubly-linked list adds a prev pointer to each node, enabling O(1) insertion and removal anywhere — given a node reference. collections.deque in Python is implemented as a doubly-linked list of fixed-size blocks.

Complexity

How it works

Each node = (value, prev, next). Sentinel head and tail nodes simplify edge cases. To remove node n: n.prev.next = n.next; n.next.prev = n.prev. To insert before node n: link the new node between n.prev and n. Both are O(1) once you hold the node reference.

Python implementation

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


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

    def push_back(self, val):           # O(1)
        n = Node(val)
        n.prev, n.next = self.tail.prev, self.tail
        self.tail.prev.next = n
        self.tail.prev = n
        self._size += 1
        return n

    def remove(self, node):             # O(1) given the node
        node.prev.next = node.next
        node.next.prev = node.prev
        self._size -= 1
        return node.val

    def __iter__(self):
        n = self.head.next
        while n is not self.tail:
            yield n.val
            n = n.next

    def __len__(self):
        return self._size


dll = DoublyLinkedList()
a = dll.push_back("a"); b = dll.push_back("b"); c = dll.push_back("c")
print(list(dll))           # ['a', 'b', 'c']
dll.remove(b)
print(list(dll))           # ['a', 'c']

Trade-offs

• O(1) insert/delete at any node (given a reference) — exactly what an LRU cache needs.
• Twice the pointer overhead of a singly-linked list.
• Still O(n) for index-based access or value search.
• Production: use collections.deque or collections.OrderedDict rather than rolling your own.

← Back to Algorithms