Doubly Linked List: Implementation with Examples

Key Insights

Doubly linked lists trade memory overhead (an extra pointer per node) for O(1) deletion of any node and bidirectional traversal—making them essential for LRU caches, undo systems, and navigation history.
The key to bug-free implementation is handling edge cases systematically: empty lists, single-node lists, and head/tail operations each require explicit pointer management.
Combining a doubly linked list with a hash map creates a powerful O(1) LRU cache—a pattern used in production systems from Redis to operating system page replacement.

Introduction to Doubly Linked Lists

A doubly linked list is a linear data structure where each node contains three components: the data, a pointer to the next node, and a pointer to the previous node. This bidirectional linking is what distinguishes it from a singly linked list.

The tradeoff is straightforward. Singly linked lists use less memory (one pointer per node instead of two), but you can only traverse forward. If you need to delete a node and you only have a reference to that node, a singly linked list forces you to traverse from the head to find the previous node—an O(n) operation. With a doubly linked list, you already have the previous pointer. Deletion becomes O(1).

This makes doubly linked lists the right choice for:

Browser history: Navigate forward and backward through pages
Undo/redo functionality: Move bidirectionally through state changes
LRU caches: Quickly move accessed items to the front and evict from the back
Music playlists: Skip forward or backward through tracks
Text editors: Cursor movement and efficient insertion/deletion

Node Structure and Class Design

Let’s build a production-ready doubly linked list. The node structure is simple—each node holds data and two pointers:

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

The list itself maintains references to both head and tail, enabling O(1) operations at either end:

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def is_empty(self):
        return self.size == 0
    
    def __len__(self):
        return self.size

Here’s the equivalent in JavaScript:

class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    isEmpty() {
        return this.size === 0;
    }
}

Maintaining a size property costs O(1) extra space but gives you O(1) length queries—a worthwhile tradeoff in most applications.

Core Operations: Insertion

Insertion requires careful pointer manipulation. The order matters: always set up the new node’s pointers before modifying existing nodes.

def insert_at_head(self, data):
    new_node = Node(data)
    
    if self.is_empty():
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    
    self.size += 1

def insert_at_tail(self, data):
    new_node = Node(data)
    
    if self.is_empty():
        self.head = new_node
        self.tail = new_node
    else:
        new_node.prev = self.tail
        self.tail.next = new_node
        self.tail = new_node
    
    self.size += 1

def insert_at_index(self, index, data):
    if index < 0 or index > self.size:
        raise IndexError("Index out of bounds")
    
    if index == 0:
        self.insert_at_head(data)
        return
    
    if index == self.size:
        self.insert_at_tail(data)
        return
    
    new_node = Node(data)
    current = self._get_node_at(index)
    
    # Insert before current
    new_node.prev = current.prev
    new_node.next = current
    current.prev.next = new_node
    current.prev = new_node
    
    self.size += 1

def _get_node_at(self, index):
    """Optimize traversal by starting from closer end."""
    if index < self.size // 2:
        current = self.head
        for _ in range(index):
            current = current.next
    else:
        current = self.tail
        for _ in range(self.size - 1 - index):
            current = current.prev
    return current

Notice _get_node_at() starts traversal from whichever end is closer. This optimization halves average traversal time for index-based operations.

Core Operations: Deletion

Deletion is where doubly linked lists shine. Given a node reference, removal is O(1):

def delete_node(self, node):
    """Delete a specific node. O(1) operation."""
    if node is None:
        return
    
    # Update previous node's next pointer
    if node.prev:
        node.prev.next = node.next
    else:
        self.head = node.next  # Deleting head
    
    # Update next node's prev pointer
    if node.next:
        node.next.prev = node.prev
    else:
        self.tail = node.prev  # Deleting tail
    
    self.size -= 1
    return node.data

def delete_at_index(self, index):
    if index < 0 or index >= self.size:
        raise IndexError("Index out of bounds")
    
    node = self._get_node_at(index)
    return self.delete_node(node)

def delete_by_value(self, value):
    """Delete first occurrence of value. Returns True if found."""
    current = self.head
    
    while current:
        if current.data == value:
            self.delete_node(current)
            return True
        current = current.next
    
    return False

The edge cases in delete_node() handle four scenarios cleanly: deleting from the middle, deleting the head, deleting the tail, and deleting the only node (which triggers both head and tail updates).

Traversal and Search

Bidirectional traversal is the defining feature of doubly linked lists:

def traverse_forward(self):
    """Yield all elements from head to tail."""
    current = self.head
    while current:
        yield current.data
        current = current.next

def traverse_backward(self):
    """Yield all elements from tail to head."""
    current = self.tail
    while current:
        yield current.data
        current = current.prev

def find(self, value):
    """Return the node containing value, or None."""
    current = self.head
    while current:
        if current.data == value:
            return current
        current = current.next
    return None

def __iter__(self):
    return self.traverse_forward()

def __repr__(self):
    return " <-> ".join(str(item) for item in self)

For ordered lists, you could optimize find() to search from both ends simultaneously, but for unordered data, this adds complexity without guaranteed benefit.

Practical Example: Building an LRU Cache

The LRU (Least Recently Used) cache is the canonical use case for doubly linked lists. The requirements are:

O(1) access to any cached item
O(1) update of recency when an item is accessed
O(1) eviction of the least recently used item

A hash map alone gives you O(1) access but can’t track ordering. A list alone can track ordering but gives O(n) access. Combined, they’re unbeatable:

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> Node
        self.list = DoublyLinkedList()
    
    def get(self, key):
        if key not in self.cache:
            return None
        
        node = self.cache[key]
        self._move_to_front(node)
        return node.data['value']
    
    def put(self, key, value):
        if key in self.cache:
            # Update existing
            node = self.cache[key]
            node.data['value'] = value
            self._move_to_front(node)
        else:
            # Add new
            if len(self.cache) >= self.capacity:
                self._evict()
            
            node_data = {'key': key, 'value': value}
            self.list.insert_at_head(node_data)
            self.cache[key] = self.list.head
    
    def _move_to_front(self, node):
        if node == self.list.head:
            return  # Already at front
        
        # Remove from current position
        self.list.delete_node(node)
        
        # Re-insert at head
        self.list.insert_at_head(node.data)
        self.cache[node.data['key']] = self.list.head
    
    def _evict(self):
        if self.list.is_empty():
            return
        
        lru_node = self.list.tail
        del self.cache[lru_node.data['key']]
        self.list.delete_node(lru_node)

Usage example:

cache = LRUCache(3)
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3)

print(cache.get("a"))  # Returns 1, moves "a" to front

cache.put("d", 4)      # Evicts "b" (least recently used)
print(cache.get("b"))  # Returns None

The most recently used items stay near the head; the least recently used drift to the tail and get evicted when capacity is exceeded.

Performance Analysis and When to Use

Here’s the complexity breakdown:

Operation	Doubly Linked List	Singly Linked List	Dynamic Array
Insert at head	O(1)	O(1)	O(n)
Insert at tail	O(1)	O(1)*	O(1)**
Insert at index	O(n)	O(n)	O(n)
Delete at head	O(1)	O(1)	O(n)
Delete at tail	O(1)	O(n)	O(1)
Delete by reference	O(1)	O(n)	O(n)
Access by index	O(n)	O(n)	O(1)
Search	O(n)	O(n)	O(n)
Memory per element	Data + 2 pointers	Data + 1 pointer	Data

*With tail pointer. **Amortized.

Use doubly linked lists when:

You need O(1) deletion given a node reference
Bidirectional traversal is required
Frequent insertions/deletions at both ends
Building LRU caches, undo systems, or navigation stacks

Use arrays when:

Random access by index is common
Memory efficiency is critical
Data is mostly read, rarely modified

Use singly linked lists when:

You only traverse forward
Memory is constrained
Simple stack/queue operations suffice

The extra pointer per node in a doubly linked list typically adds 8 bytes on 64-bit systems. For a million nodes, that’s 8MB of overhead. For most applications, this is negligible. For embedded systems or massive datasets, it might matter.

Doubly linked lists aren’t the answer to every problem, but when you need their specific capabilities—bidirectional traversal and O(1) arbitrary deletion—nothing else comes close.