Lesson 11 · Linear structures

Doubly Linked Lists

A doubly linked list node contains two pointers: one to the next node and one to the previous node. This allows for bidirectional traversal and simplifies deletions, but requires managing twice as many connections.

The Bidirectional Advantage

In a singly linked list, if you are given a node and told to delete it, you cannot do it cleanly because you don't know the node before it.

With a doubly linked list, every node knows its predecessor. You can delete any node in O(1) time simply by connecting its prev node directly to its next node.

Contains next and prev pointers
Allows reverse traversal
Deletions only require the node itself

Pointer Management overhead

The power of two pointers comes with complexity. Every time you insert or remove a node, you must successfully update four different pointers.

Failing to update a prev pointer on a neighboring node is a very common source of bugs, leaving the list structurally broken if traversed backwards.

Insertions require 4 pointer reassignments
Deletions require 2 pointer reassignments
Requires more memory per node

Key reference

Terms, operations, and practical uses

Pointer mechanics

Previous Pointer (prev)An additional reference in every node that points to the node immediately behind it.
Bidirectional TraversalThe ability to walk the list backward from tail to head, impossible in a singly linked list.
O(1) DeletionRemoving a node instantly if you hold a reference to it, by bridging its prev and next nodes together.

Structure management

Tail PointerA reference to the very last node, allowing O(1) insertions at the end and backward traversal.
Sentinel NodesUsing both a dummy head and dummy tail to ensure every real node has a non-null prev and next, eliminating edge cases.
Pointer ReassignmentThe complex process of updating four different pointers to safely insert a node between two others.

Real-world uses

LRU CacheLeast Recently Used cache. Combines a hash map with a doubly linked list to evict the oldest item in O(1) time.
Browser HistoryStoring web pages so the user can freely step backward and forward through their visited sites.
Undo/Redo BuffersAllowing users to traverse backward through their action history, and forward if they redo.

Code example

O(1) Deletion in a Doubly Linked List

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

def delete_node(node_to_delete):
    # Assumes dummy head and tail exist so prev/next are never null
    node_to_delete.prev.next = node_to_delete.next
    node_to_delete.next.prev = node_to_delete.prev
    node_to_delete.prev = None
    node_to_delete.next = None
one, two, three, four = Node(1), Node(2), Node(3), Node(4)
for a, b in ((one, two), (two, three), (three, four)):
    a.next, b.prev = b, a

delete_node(three)
parts, node = [], one
while node:
    parts.append(str(node.val))
    node = node.next
print('List becomes ' + ' <-> '.join(parts))

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* prev;
    Node* next;
    Node(int x) : val(x), prev(NULL), next(NULL) {}
};

void deleteNode(Node* node_to_delete) {
    // Assumes dummy head and tail exist
    node_to_delete->prev->next = node_to_delete->next;
    node_to_delete->next->prev = node_to_delete->prev;
    node_to_delete->prev = NULL;
    node_to_delete->next = NULL;
}

class Main {
    static class Node {
        int val;
        Node prev, next;
        Node(int x) { val = x; }
    }
    public static void deleteNode(Node nodeToDelete) {
        // Assumes dummy head and tail exist
        nodeToDelete.prev.next = nodeToDelete.next;
        nodeToDelete.next.prev = nodeToDelete.prev;
        nodeToDelete.prev = null;
        nodeToDelete.next = null;
    }
}

InputDelete node 3 from 1 <-> 2 <-> 3 <-> 4

OutputList becomes 1 <-> 2 <-> 4

Example

Run the example step by step

Output

Sentinel Nodes (Dummy Nodes)

To simplify edge cases (like inserting at the absolute beginning or deleting the last node), doubly linked lists heavily utilize sentinel nodes.

By keeping a dummy head and dummy tail node that contain no actual data, you guarantee that every real node always has a valid prev and next, eliminating the need to check for null.

Dummy head and tail nodes
Eliminates if (head == null) checks
Makes all operations uniform

Application: LRU Cache

The Least Recently Used (LRU) Cache is one of the most famous applications of a doubly linked list, combined with a hash map.

The hash map provides O(1) access to the nodes, while the doubly linked list allows you to sever a node from the middle and move it to the front in O(1) time whenever it is accessed.

Hash Map + Doubly Linked List
O(1) lookups and O(1) evictions
Nodes are constantly moved to the 'recent' end