Doubly Linked List Implementation

Hello! Welcome to the second lesson in our module on implementing core data structures.

In our previous lesson, we built a hash map that could dynamically resize itself, introducing the concepts of load factor and amortized analysis. We concluded by noting that to build a high-performance LRU cache—a common interview topic and a practical system component—we need one more piece: a doubly linked list.

Today, we will focus on this exact learning outcome: Implement a doubly linked list supporting efficient insertion, deletion, and move-to-end operations.

This lesson is a direct stepping stone to our goal. A doubly linked list provides the crucial O(1) reordering capability that a cache needs to track recency of use. While your work on schedulers like Rudi at AWS involved managing priorities in queues, you'll find that the pointer manipulation in a doubly linked list offers a different but equally powerful way to manage ordered data, especially when items need to be moved around frequently.

We will start with the basic structure and then quickly move to a more robust, production-oriented implementation using a technique called sentinel nodes, which simplifies the code by elegantly handling edge cases.

1. Anatomy of a Doubly Linked List

A singly linked list connects nodes in one direction. A doubly linked list (DLL), as the name implies, adds a second link, pointing to the previous node.

This bidirectional linkage is the key feature. It means that from any given node, you can traverse both forward and backward. In Python, a node is typically represented by a simple class:

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

(We're including key and value in anticipation of using this Node for our future LRU cache, where it will store key-value pairs.)

The primary trade-offs compared to other data structures are:

• vs. Singly Linked List: A DLL uses slightly more memory due to the extra prev pointer. In return, it allows for O(1) deletion of a node if you have its reference (a singly linked list would need O(N) to find the preceding node) and efficient traversal in both directions.
• vs. Python list (Dynamic Array): A DLL has O(1) insertion and deletion anywhere in the list (given a node reference), whereas an array requires O(N) for these operations as elements must be shifted. However, a DLL has O(N) access by index, while an array provides O(1) access.

2. The Challenge of Edge Cases

Let's consider the logic for removing a node from a DLL. You need to handle several cases:

• Is the list empty?
• Is the node to be removed the only node in the list?
• Is it the head of the list?
• Is it the tail of the list?
• Is it somewhere in the middle?

Each case requires slightly different pointer updates and null checks. For instance, to remove the head, you update the list's head pointer and set the new head's prev to None. To remove a middle node, you connect its prev and next nodes to each other. This leads to code with many if/else statements, which can be complex and error-prone.

To see this in action, the following video walks through the pointer manipulation for various operations. Notice the special handling required at the boundaries of the list.

This complexity is precisely what we want to avoid in a clean, production-ready implementation.

3. A More Robust Implementation: Sentinel Nodes

A professional approach to building a DLL is to use sentinel nodes (also called dummy nodes). Instead of having head and tail pointers that can be None, we initialize the list with two permanent, empty nodes: a dummy head and a dummy tail.

These sentinels act as fixed bookends for our list. The "real" content of the list always lives between them.

The key advantages are:

1. The list is never "empty" in a structural sense; it always contains the head and tail sentinels.
2. Every real data node is guaranteed to have a non-null prev (a sentinel or another data node) and a non-null next.
3. Insertion and deletion logic becomes universal. There are no more special cases for the start, end, or middle of the list. The same logic works everywhere.

Let's study a concise, high-quality implementation that uses this pattern. The code is part of an LRU Cache implementation, which is exactly where we're heading.

4. Implementing the Doubly Linked List

Now, let's build our own DoublyLinkedList class based on the sentinel node pattern. The internal methods _add_node and _remove_node contain the core logic, making our public-facing API simple and declarative.

Note that the _add_node from the article always adds to the front. We'll rename it _add_to_head for clarity and add a corresponding _add_to_tail.

import threading
from typing import Optional

class Node:
    """A node in a doubly linked list."""
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev: Optional[Node] = None
        self.next: Optional[Node] = None

    def __repr__(self):
        return f"Node(key={self.key}, value={self.value})"

class DoublyLinkedList:
    """
    A doubly linked list implementation using sentinel nodes.
    This simplifies insertion and deletion by removing edge cases.
    """
    def __init__(self):



        # Sentinel nodes to simplify boundary conditions.
        # The actual content is between head.next and tail.prev.
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove_node(self, node: Node):
        """Internal method to remove a node from the list in O(1)."""
        prev_node = node.prev
        next_node = node.next
        prev_node.next = next_node
        next_node.prev = prev_node

    def _add_to_head(self, node: Node):
        """Internal method to add a node to the head of the list in O(1)."""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        
    def _add_to_tail(self, node: Node):
        """Internal method to add a node to the tail of the list in O(1)."""
        node.next = self.tail
        node.prev = self.tail.prev
        self.tail.prev.next = node
        self.tail.prev = node




    # --- Public API ---

    def prepend(self, node: Node):
        """Adds a node to the beginning of the list."""
        self._add_to_head(node)

    def append(self, node: Node):
        """Adds a node to the end of the list."""
        self._add_to_tail(node)

    def remove(self, node: Node):
        """Removes a given node from the list."""
        self._remove_node(node)

    def move_to_head(self, node: Node):
        """Moves an existing node to the head of the list."""
        self._remove_node(node)
        self._add_to_head(node)
        
    def pop_tail(self) -> Optional[Node]:
        """Removes and returns the last node in the list."""
        if self.head.next == self.tail:
            return None # List is empty
        last_node = self.tail.prev
        self._remove_node(last_node)
        return last_node

    def __str__(self):
        """Allows printing the list's contents for debugging."""
        nodes = []
        current = self.head.next
        while current != self.tail:
            nodes.append(str(current.value))
            current = current.next
        return " <-> ".join(["HEAD"] + nodes + ["TAIL"])

Analysis of Key Operations:

• prepend / append / remove: Because we have a reference to the node (and the sentinels head and tail), these are all O(1) operations. The number of pointer re-assignments is constant, regardless of the list's size.
• move_to_head: This is the operation we need for our LRU cache. It is a composition of _remove_node (O(1)) and _add_to_head (O(1)). Therefore, the entire move_to_head operation is also O(1). This is incredibly efficient and is the primary reason for using a DLL in this context.
• Searching: If you needed to find a node by its value, you would still have to traverse the list, which is an O(N) operation. This highlights why for an LRU cache, we need a companion data structure—our hash map—to get a reference to the node in O(1) time.

Conclusion

In this lesson, you have implemented a robust, production-minded doubly linked list. You have gone beyond a basic implementation by using sentinel nodes to create cleaner, more maintainable code that eliminates tricky edge cases.

Key Takeaways:

• A doubly linked list provides O(1) time complexity for insertion and deletion operations when a reference to the target node is available.
• The use of sentinel nodes (dummy head and tail) is a powerful pattern that standardizes list operations, making the code simpler and less error-prone.
• The crucial move_to_head operation is also O(1), making the DLL the perfect choice for managing the recency order in a cache.
• The main trade-offs are increased memory per node (for the prev pointer) and O(N) time for access by index or search by value.

Next Lesson Preview

We have now built and analyzed the two fundamental components required for a high-performance cache:

1. A resizable hash map for O(1) average-time lookups.
2. A doubly linked list for O(1) ordering operations.

In our next lesson, we will combine these two to achieve the main goal of this module: implementing a thread-safe, production-quality LRU Cache from scratch. You will see how these two data structures work together to provide both fast access and efficient eviction.