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.

The extra pointer costs memory, but it removes the main weakness of a singly linked list: there, deleting a node requires its predecessor, which you can only find by walking from the head. With prev available, any node can unlink itself in constant time, and the list can be traversed in both directions. That property is why doubly linked lists sit inside LRU caches, browser history, text-editor buffers, and the free lists of memory allocators.

Structure and sentinels

Doubly linked list with sentinel head and tail head sentinel val = None a prev = head next = b b prev = a next = c c prev = b next = tail tail sentinel val = None Arrows show next pointers; every node also stores prev, pointing back to its left neighbour.

The two sentinel nodes never hold data. Because a real node always has a real prev and next (possibly a sentinel), insert and remove never need to test for None or special-case an empty list, the first element, or the last element. An empty list is simply head.next is tail. This removes the most common source of linked-list bugs at the cost of two extra nodes.

Step-by-step: removing a node

remove(b): two pointer updates Before head a b c tail 1. a.next = b.next (a points to c) head a c tail 2. c.prev = b.prev (c points to a) head a c tail Result: b unreachable, size 2 head a c tail No traversal is needed: the node itself supplies both neighbours, so removal is O(1).

The two assignments are the whole operation. After them, nothing in the list refers to b, so Python's garbage collector reclaims it once the caller drops its reference. Insertion is the mirror image: set the new node's prev and next, then patch the neighbours' pointers to it. The order matters only in that you must read b.prev and b.next before overwriting anything that holds them.

Complexity

Average Worst Space
AccessSearchInsertionDeletion AccessSearchInsertionDeletion Worst
Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

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

Worked example: an LRU cache

An LRU (least recently used) cache needs O(1) lookup, O(1) "mark as recently used", and O(1) eviction of the oldest entry. A dictionary gives the lookup; a doubly linked list ordered by recency gives the other two, because a node found through the dictionary can be unlinked and moved to the back without searching.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}                      # key -> node
        self.list = DoublyLinkedList()     # front = least recent, back = most recent

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self.list.remove(node)             # O(1)
        self.map[key] = self.list.push_back(node.val)
        return node.val[1]

    def put(self, key, value):
        if key in self.map:
            self.list.remove(self.map[key])
        elif len(self.list) == self.capacity:
            oldest = self.list.head.next   # first real node
            self.list.remove(oldest)
            del self.map[oldest.val[0]]
        self.map[key] = self.list.push_back((key, value))


cache = LRUCache(2)
cache.put("x", 1); cache.put("y", 2)
cache.get("x")            # x is now most recent
cache.put("z", 3)         # evicts y
print(cache.get("y"), cache.get("x"), cache.get("z"))   # None 1 3

In production Python the same structure is available as collections.OrderedDict with move_to_end() and popitem(last=False), or simply functools.lru_cache for memoizing functions.

When to choose a doubly linked list. Use one when the program already holds references to elements and must delete or reorder them frequently, when it needs efficient operations at both ends, or when it walks forward and backward through a sequence, as an undo/redo history does. Choose a dynamic array (a Python list) when access is mostly by index or by full scans, since contiguous memory and lower per-element overhead win there. Choose a singly linked list when only forward traversal and front insertion are required and memory is tight, since each node then carries one pointer instead of two.

Pitfalls

← Back to Algorithms