Doubly Linked Lists

# CHAPTER 9

Doubly Linked Lists #

1. Introduction #

2. Learning Objectives #

• Define the architectural structure of a Doubly Linked Node.

• Traverse a data structure mathematically backward.

• Manage the complex pointer logic required to insert and delete bidirectional nodes.

• Identify the Space/Time trade-offs of Doubly Linked architectures.

3. The Architecture: Two Pointers #

Visualizing the Structure:

      NULL <- [prev | 10 | next] <-> [prev | 20 | next] <-> [prev | 30 | next] -> NULL
                (Head Node)                                      (Tail Node)

• The prev pointer of the Head is NULL (Nothing comes before it).

• The next pointer of the Tail is NULL (Nothing comes after it).

• All internal Nodes are securely locked together in both directions.

4. Defining a Doubly Linked Node in Code #

// Java Example: Doubly Linked Node
class Node {
    int data;
    Node next; // Points to the future
    Node prev; // Points to the past!

    // Constructor
    public Node(int d) {
        data = d;
        next = null;
        prev = null;
    }
}

5. Bidirectional Traversal #

// C++ Example: Reverse Traversal
void traverseBackward(Node* tail) {
    Node* current = tail;
    
    // Loop until we hit the Head's prev pointer (NULL)
    while (current != NULL) {
        cout << current->data << " ";
        current = current->prev; // MOVE BACKWARD!
    }
}

6. The Cost of Bidirectional Logic #

#### 6.1 Insertion (Between Node A and Node C) Let's insert Node B.

1. 1. Set B.next to point to C.

1. 2. Set B.prev to point to A.

1. 3. Set C.prev to point backward to B.

1. 4. Set A.next to point forward to B.

# Python Example: Insert After a specific Node
def insert_after(self, prev_node, new_data):
    if prev_node is None:
        return
        
    # 1. Create the new node
    new_node = Node(new_data)
    
    # 2 & 3. Wire the new node to its neighbors
    new_node.next = prev_node.next
    new_node.prev = prev_node
    
    # 4. Wire the subsequent node backward to the new node
    if prev_node.next is not None:
        prev_node.next.prev = new_node
        
    # 5. Wire the previous node forward to the new node
    prev_node.next = new_node

7. Advantages and Disadvantages #

Advantages:

• Reverse Traversal: Perfect for Undo/Redo features, Browser History, and Music Playlists.

• O(1) Deletion from a pointer: If you are given a pointer to the exact Node you want to delete, you can delete it in O(1) time! (In a Singly Linked List, even if you hold the target Node, you still have to traverse O(n) from the Head to find the *previous* Node to rewire the chain).

Disadvantages:

• Higher Space Complexity: Every single Node requires an extra 64-bits (8 bytes) of RAM strictly to hold the prev memory address. Across millions of Nodes, this memory overhead is massive.

• Vulnerability to Bugs: With twice as many pointers to manage during insert and delete, the risk of throwing a fatal NullPointerException or breaking the chain doubles.

8. Mini Project: Browser History Manager #

// Java: Conceptual Browser History
public class BrowserHistory {
    Node current_page;
    
    public void visitNewPage(String url) {
        Node newPage = new Node(url);
        newPage.prev = current_page;
        if (current_page != null) {
            current_page.next = newPage;
        }
        current_page = newPage; // Move forward
        System.out.println("Visited: " + url);
    }
    
    public void clickBackButton() {
        if (current_page.prev != null) {
            current_page = current_page.prev; // Move backward!
            System.out.println("Went back to: " + current_page.data);
        } else {
            System.out.println("Cannot go back. This is the first page.");
        }
    }
}

9. Common Mistakes #

• Forgetting to update the prev pointer: When inserting a node, junior developers often perfectly wire the forward next pointers, but forget to wire the backward prev pointers. The data structure will traverse perfectly from Head to Tail, but traversing from Tail to Head will instantly derail and crash!

10. Best Practices #

• Garbage Collection Safety: When deleting a Node from a Doubly Linked List in a language with Garbage Collection (like Java or C#), explicitly set the deleted Node's next and prev pointers to null. If you leave them attached to the live list, the Garbage Collector might refuse to delete the floating node, causing a Memory Leak.

11. Exercises #

1. 1. Write the code block required to delete a target Node from the exact middle of a Doubly Linked List. How many pointers must you rewire?

1. 2. Explain why a Doubly Linked List is the perfect underlying structure for implementing a Least Recently Used (LRU) Cache algorithm.

12. MCQs with Answers #

13. Interview Preparation #

• *System Design:* "Design the underlying data structure for a Least Recently Used (LRU) Cache mechanism utilized by an enterprise Database. Why is combining a Hash Map with a Doubly Linked List the optimal architectural choice to achieve O(1) evictions?"

• *Algorithmic Coding:* "Write a function to Reverse a Doubly Linked List. How does the logic differ from reversing a Singly Linked List?" *(Answer: It's actually much easier! You just traverse the list and swap the next and prev pointers of every single node!).*

Common Pitfalls:

• In whiteboard interviews, failing to draw the arrows before writing the code. Always draw three boxes on the whiteboard, draw the forward and backward arrows, and trace exactly which arrow breaks and moves during an insertion. Do not attempt to hold pointer logic purely in your head.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #