Up until now, we've dealt with Singly Linked Lists, which are great for simple queues or stacks. But the moment you need to move backward—think of a music playlist where you want to hit "Previous," or a browser history where you click the back button—a Singly Linked List becomes a nightmare. You'd have to start from the head and traverse the entire list just to find the element before your current one. That's $O(n)$ for a move that should feel instantaneous.

To fix this, we implement a Doubly Linked List (DLL). The concept is simple: every node gets a second pointer called prev. While it sounds trivial, this is where a lot of developers trip up during implementation because you've effectively doubled the number of pointers you have to manage during every single mutation.

The "Forgot the Backlink" Bug

When I first started writing these, I made the classic mistake of treating a Doubly Linked List like a Singly Linked List with an optional extra field. I'd write an addLast method that correctly updated the next pointer of the current tail, but I'd forget to point the new node's prev back to that tail. The code would compile, and the list would even seem to work if you only traversed it forward.

// The naive/buggy approach
public void addLast(T data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = tail = newNode;
    } else {
        tail.next = newNode; // Forward link is set
        tail = newNode;      // Tail is moved
        // ERROR: newNode.prev is still null! 
        // The chain is broken in reverse.
    }
}

The problem here is that you've created a "one-way street" in a system that promises two-way traffic. If you tried to iterate backward from the tail, you'd hit a NullPointerException immediately after the first element. This is the most common failure point in DLLs: failing to treat the next and prev updates as a single, atomic operation.

Maintaining the Bi-directional Contract

The better way to handle this is to think of every insertion or deletion as "stitching." You aren't just adding a node; you are rewriting the relationship between three different entities: the node before, the node being added, and the node after. I find it helpful to explicitly write out the pointer updates in a specific order to ensure nothing is lost to the garbage collector before it's used.

If we're adding to the end of the list, we must ensure the new node knows who its predecessor is before we move the tail pointer. Here is how I'd implement a robust addLast:

public void addLast(T data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = tail = newNode;
        return;
    }
    
    newNode.prev = tail;    // 1. Link new node back to current tail
    tail.next = newNode;    // 2. Link current tail forward to new node
    tail = newNode;         // 3. Update the tail reference
}

This pattern holds true for deletions as well. When removing a node in the middle, you have to "bridge" the gap. The node before the target must point to the node after the target, and vice versa. If you miss either one, you've corrupted the list. I always recommend drawing this out on a whiteboard or a piece of paper first; it's much easier to see a missing arrow in a diagram than it is to find a null pointer in a 500-line class.

The Memory Tax for Flexibility

Now, you might be wondering why we don't just use Doubly Linked Lists for everything. There's a trade-off here: memory. In a 64-bit JVM, every reference takes up space. By adding a prev pointer to every single node, you're increasing the memory footprint of your list. For a list with a few hundred elements, it's negligible. For a list with millions of small objects, that extra reference per node can lead to significantly higher heap usage and more frequent GC pauses.

I generally tell my team: use a Singly Linked List if you're implementing a basic queue where you only ever touch the head and tail. Use a Doubly Linked List if you need to delete nodes in the middle of the list efficiently (given you already have a reference to the node) or if you need bi-directional navigation. The $O(1)$ deletion of a known node is the real "killer feature" of the DLL, because you don't have to search for the predecessor node to bridge the gap—the node already knows who its predecessor is.

📋 Practical Task

Implementation: Browser History Navigation System

Build a BrowserHistory class that uses a Doubly Linked List to simulate a web browser's back and forward functionality. You should not use Java's built-in LinkedList class; instead, implement your own internal Node class to handle the prev and next references.

Your class must implement the following functionality:

• void visit(String url): Adds a new URL to the history. Importantly, if the user is currently in the middle of their history (having gone "back") and visits a new page, all "forward" history must be deleted.
• String back(int steps): Moves backward in history by the specified number of steps (or to the very first page if steps exceed the history) and returns the current URL.
• String forward(int steps): Moves forward in history by the specified number of steps (or to the most recent page) and returns the current URL.

Constraint: Ensure that your visit method correctly updates both the next and prev pointers to prevent memory leaks and maintain the integrity of the bi-directional chain.