Previous Topic

What Is a Doubly Linked List?

A doubly linked list (DLL) is a sequence of nodes where each node stores:

• data: the payload
• prev: a reference to the previous node
• next: a reference to the next node

Because nodes link in both directions, you can traverse forward and backward and perform insertions/deletions in O(1) time when you already have a reference to the node at the insertion/deletion point.

Node Structure

// C-like
struct Node {
    int value;
    Node* prev;
    Node* next;
};

struct List {
    Node* head;
    Node* tail;
    size_t size;
};

Maintaining head and tail pointers allows O(1) insertion/removal at both ends.

Core Operations and Complexities

• Insert at head/tail: O(1)
• Insert before/after a known node: O(1)
• Delete a known node: O(1)
• Search by value: O(n)
• Traverse forward/backward: O(n)

Insert at Head

function push_front(list, x):
    n = new Node(x)
    n.prev = null
    n.next = list.head
    if list.head != null:
        list.head.prev = n
    else:
        list.tail = n  // list was empty
    list.head = n
    list.size++

Insert After a Given Node

function insert_after(node, x, list):
    n = new Node(x)
    n.prev = node
    n.next = node.next
    if node.next != null:
        node.next.prev = n
    else:
        list.tail = n
    node.next = n
    list.size++

Delete a Given Node

function erase(node, list):
    if node.prev != null:
        node.prev.next = node.next
    else:
        list.head = node.next
    if node.next != null:
        node.next.prev = node.prev
    else:
        list.tail = node.prev
    free(node)
    list.size--

Use Cases

• Deques: efficient push/pop at both ends.
• LRU caches: move accessed items to front; evict from back.
• Undo/redo: navigate backward/forward through history.
• Browser history: back and forward navigation.
• Text editor buffers: cursor-local edits in gap/rope-like structures.

Trade-offs vs Other Structures

• Vs arrays/dynamic arrays: DLLs excel at O(1) insertion/deletion with a node reference, but lack O(1) random access and have worse cache locality.
• Vs singly linked lists: DLLs support reverse traversal and O(1) delete with only a node pointer (no predecessor search), but use extra memory and require more pointer maintenance.

Variants

• Circular DLL: tail.next = head and head.prev = tail simplify some edge cases.
• Sentinel (dummy) nodes: a non-data head/tail reduces null checks and unifies logic.
• Intrusive lists: nodes embed link fields directly in payload objects to avoid extra allocation.

Common Pitfalls

• Forgetting to update both prev and next links during insert/delete.
• Not handling edge cases: empty list, single-node list, removing head/tail.
• Memory management errors in manual memory languages (leaks, double frees, dangling pointers).
• Iterator invalidation when nodes are removed or moved.

Language Considerations

• C/C++: Manual memory management; consider RAII in C++ and use std::list for safety. Be mindful of allocator overhead and iterator invalidation rules.
• Java: LinkedList<T> is typically a doubly linked list; garbage collection handles reclamation.
• Python: collections.deque is a high-performance double-ended queue (not a pure DLL implementation but similar use cases). A custom DLL can be built with classes.

Example: Reverse Traversal

function traverse_backward(list):
    cur = list.tail
    while cur != null:
        visit(cur.value)
        cur = cur.prev

Testing Tips

• After each operation, verify list invariants: correct head/tail, matching prev/next pairs, accurate size.
• Stress test: insert/delete sequences, random operations, and checks for memory safety where applicable.

When to Use

Choose a doubly linked list when you need frequent insertions/deletions at arbitrary positions with node references, bidirectional traversal, or list reordering (move-to-front) — and you can tolerate extra pointer memory and reduced cache locality compared to arrays.

Next Topic