Doubly Linked ListDoubly linked lists

01Why it exists

Reach for it when you see:LRU, recency of use, operations at both ends, O(1) removal of an arbitrary node you already hold, previous and next, undo/redo.

02The core idea

In a doubly linked list, every node records one extra pointer, prev. That single pointer buys one crucial ability: given a node, you can unlink it from the list in O(1). A singly linked list cannot, because it has no idea which node comes before, so it has to search again from the head — O(n).

The price is that every insertion and deletion touches four pointers instead of two, and it is correspondingly easier to wire up wrongly. The standard remedy is two sentinels: head and tail always exist, never hold data, and every real node lives between them. That way every real node is guaranteed to have both a prev and a next, so inserting at the front and deleting the last element need no special cases.

The classic use of a doubly linked list is pairing it with a hash table to build an LRU cache: the hash table handles "find the node for this key" in O(1), the list handles "keep the usage order", and each structure covers the other's weakness. This hash-table-plus-list combination shows up again in OrderedDict, in LFU caches, and in plenty of other places that need to find something fast and then reorder it fast.

03The algorithm

1. 1Create two sentinels: head.next = tail and tail.prev = head. Real nodes always sit between them.
2. 2Unlink a node n: n.prev.next = n.next and n.next.prev = n.prev. Leaving n's own pointers alone is fine, since it is about to be relinked or discarded.
3. 3Push to the front: set n's two pointers first (n.next = head.next, n.prev = head), then fix up the neighbours (head.next.prev = n, head.next = n). Yourself first, then everyone else.
4. 4LRU get: look the node up in the hash table, unlink it, push it to the front, and return its value. Return −1 when the key is absent.
5. 5LRU put: if the key exists, update the value and move the node to the front; if it does not and the cache is full, unlink tail.prev (the least recently used) and delete it from the hash table first, then create the new node, push it to the front, and record it in the hash table.

04Interactive demo

An LRU cache with capacity 3. put or get on a key moves it to the front; putting a new key into a full cache evicts the least recently used node at the tail. The hash table on the right points each key straight at its node in the list.

05Code

The Python version writes the nodes and the two sentinels by hand; once unlink and push_front are factored out, get and put are nothing but combinations of them. The C++ version uses std::list with splice, which does the O(1) move in a single line.

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


class LRUCache:
    """A doubly linked list holds the usage order (most recent at the head); a hash table finds a node in O(1)."""

    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                      # key → Node
        self.head, self.tail = Node(), Node()   # two sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    # --- the two O(1) list operations ---
    def _unlink(self, node):
        node.prev.next = node.next         # having prev is what makes unlinking yourself O(1)
        node.next.prev = node.prev

    def _push_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    # --- public interface ---
    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._unlink(node)                 # move to the front = just used
        self._push_front(node)
        return node.val

    def put(self, key, val):
        if key in self.map:
            node = self.map[key]
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev           # the least recently used sits at the tail
            self._unlink(lru)
            del self.map[lru.key]
        node = Node(key, val)
        self._push_front(node)
        self.map[key] = node


# Python's built-in deque and OrderedDict are doubly linked lists underneath
from collections import deque, OrderedDict
d = deque([1, 2, 3])
d.appendleft(0)      # O(1)
d.pop()              # O(1)

06Practice

• LeetCode 146LRU CacheMedium
• LeetCode 641Design Circular DequeMedium
• LeetCode 430Flatten a Multilevel Doubly Linked ListMedium
• LeetCode 1472Design Browser HistoryMedium
• LeetCode 460LFU Cache (a hash table plus several doubly linked lists)Hard