Doubly Linked List

doubly-linked-list: The Ultimate Cheatsheet

1. Detailed Explanation

A doubly-linked list is a linear data structure where each element (node) points to both its next and previous nodes in the sequence. Unlike a singly-linked list, this bidirectional linking allows traversal in both directions. Each node typically contains three parts: data, a pointer to the next node, and a pointer to the previous node. The list is often maintained with pointers to the head (first node) and tail (last node) for efficient insertion and deletion at both ends.

Importance and Problem Solving: Doubly-linked lists are valuable when efficient insertion and deletion are needed at arbitrary positions within the list, and bidirectional traversal is required. They’re particularly useful in applications where you need to move back and forth through the data easily, such as:

• Undo/Redo functionality: Maintaining a history of actions.
• LRU (Least Recently Used) cache: Tracking the order of cache access.
• Implementing advanced data structures: As building blocks for more complex structures.

Core Concepts and Terminology:

• Node: An individual element in the list, containing data and pointers to the next and previous nodes.
• Head: A pointer to the first node in the list.
• Tail: A pointer to the last node in the list.
• Next Pointer: A pointer within a node pointing to the next node in the sequence.
• Previous Pointer: A pointer within a node pointing to the previous node in the sequence.

2. When to Use doubly-linked-list (and When Not To)

Use doubly-linked lists when:

• You need to frequently insert or delete nodes at arbitrary positions.
• Bidirectional traversal is essential for your algorithm.
• You need to maintain a readily accessible order of elements.

Don’t use doubly-linked lists when:

• Random access is crucial (arrays are much faster).
• Memory efficiency is paramount (they consume more memory than singly-linked lists due to the extra pointer).
• You only need to traverse in one direction (a singly-linked list is sufficient).

3. Core Algorithm / Data Structure Template

Insertion (at a specific node):

1. Create a new node with the desired data.
2. Adjust the next and previous pointers of the new node to point to the node before and after the insertion point, respectively.
3. Update the next and previous pointers of the surrounding nodes to point to the new node.

Deletion (of a specific node):

1. Adjust the next pointer of the node before the target node to point to the node after the target node.
2. Adjust the previous pointer of the node after the target node to point to the node before the target node.
3. Delete the target node.

4. Code Implementations

Python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def prepend(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def delete(self, node):
        if not node:
            return
        if node == self.head:
            self.head = node.next
        if node == self.tail:
            self.tail = node.prev
        if node.prev:
            node.prev.next = node.next
        if node.next:
            node.next.prev = node.prev
        del node

Java

class Node {
    int data;
    Node next;
    Node prev;

    Node(int d) {
        data = d;
    }
}

class DoublyLinkedList {
    Node head;

    void append(int new_data) {
        Node new_node = new Node(new_data);
        new_node.next = null;

        if (head == null) {
            head = new_node;
            return;
        }
        Node last = head;
        while (last.next != null)
            last = last.next;
        last.next = new_node;
        new_node.prev = last;
    }

    // ... other methods (prepend, delete, etc.) would go here ...
}

C++

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node* prev;
};

class DoublyLinkedList {
public:
    Node* head;

    DoublyLinkedList() : head(nullptr) {}

    void append(int new_data) {
        Node* new_node = new Node{new_data, nullptr, nullptr};
        if (head == nullptr) {
            head = new_node;
            return;
        }
        Node* last = head;
        while (last->next != nullptr)
            last = last->next;
        last->next = new_node;
        new_node->prev = last;
    }

    // ... other methods (prepend, delete, etc.) would go here ...
};

5. Complexity Analysis

Operation	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Access (by index)	O(n)	O(n)	O(n)	O(1)
Search	O(1) (head/tail)	O(n)	O(n)	O(1)
Insertion	O(1) (head/tail)	O(n)	O(n)	O(1)
Deletion	O(1) (head/tail)	O(n)	O(n)	O(1)

6. Pro Tips, Tricks, and Common Pitfalls

Pro Tips:

• Sentinel Nodes: Adding dummy nodes at the head and tail can simplify many operations by eliminating null pointer checks.
• Iterators: Creating custom iterators can make traversing and manipulating the list more elegant and readable.

Common Pitfalls:

• Null Pointer Dereferences: Always check for null or nullptr before accessing next or prev pointers.
• Double Deletion: Ensure you don’t accidentally delete a node more than once.
• Incorrect Pointer Updates: Carefully manage pointer updates during insertion and deletion to avoid creating cycles or breaking the list’s integrity.
• Memory Leaks: Remember to deallocate memory for deleted nodes (especially in C++).

7. Classic Problem Examples

Example: Convert Binary Search Tree to Sorted Doubly Linked List

Description: Given a Binary Search Tree (BST), convert it to a sorted doubly linked list. The left and right pointers in nodes should be converted to previous and next pointers in doubly linked list nodes.

High-Level Approach:

1. Perform an inorder traversal of the BST. Inorder traversal visits nodes in ascending order for a BST.
2. During the inorder traversal, create a new doubly linked list node for each BST node encountered.
3. Link the newly created doubly linked list nodes together, maintaining the sorted order established by the inorder traversal. The inorder traversal naturally provides the sorted order.
4. The head and tail of the newly created doubly linked list will point to the smallest and largest nodes from the BST respectively.

This approach leverages the inherent sorted nature of a BST’s inorder traversal to efficiently create a sorted doubly linked list. The time complexity is O(N), where N is the number of nodes in the BST, due to the single inorder traversal. The space complexity is O(N) in the worst case if the BST is skewed, as the recursive call stack might need to store N nodes. For a balanced BST, the space complexity would be O(log N) due to the depth of the tree.