Doubly Linked Lists & Circular Linked Lists

A singly linked list only lets you walk forward. If you need to go backwards — delete the previous node, traverse in reverse, or maintain a two-way relationship — you need a doubly linked list (DLL). Every node carries an extra pointer, and that one pointer changes the entire set of operations you can perform efficiently.

What is a Doubly Linked List?

A doubly linked list is a sequence of nodes where each node stores three things:

1. prev — a reference to the previous node (or None for the head)
2. data — the value stored in the node
3. next — a reference to the next node (or None for the tail)

This bidirectional linking means you can traverse the list in both directions, and you can delete any node in O(1) if you already have a reference to it — something a singly linked list cannot do.

The Node class

class DLLNode:
    """A node in a doubly linked list."""
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

    def __repr__(self):
        return f"DLLNode({self.data})"

Full Doubly Linked List Implementation

Let’s build a complete implementation with all the essential operations:

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

    def __len__(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    # ---------- Insertion ----------

    def insert_at_head(self, data):
        """Insert a new node at the beginning. O(1)."""
        new_node = DLLNode(data)
        if self.is_empty():
            self.head = 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):
        """Insert a new node at the end. O(1)."""
        new_node = DLLNode(data)
        if self.is_empty():
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1

    def insert_after(self, target_node, data):
        """Insert a new node after a given node. O(1)."""
        if target_node is None:
            raise ValueError("Target node cannot be None")

        new_node = DLLNode(data)
        new_node.prev = target_node
        new_node.next = target_node.next

        if target_node.next:
            target_node.next.prev = new_node
        else:
            # target_node was the tail
            self.tail = new_node

        target_node.next = new_node
        self.size += 1

    def insert_before(self, target_node, data):
        """Insert a new node before a given node. O(1)."""
        if target_node is None:
            raise ValueError("Target node cannot be None")

        new_node = DLLNode(data)
        new_node.next = target_node
        new_node.prev = target_node.prev

        if target_node.prev:
            target_node.prev.next = new_node
        else:
            # target_node was the head
            self.head = new_node

        target_node.prev = new_node
        self.size += 1

    # ---------- Deletion ----------

    def delete_node(self, node):
        """Remove a node from the list. O(1) with direct reference."""
        if node is None:
            raise ValueError("Cannot delete None")

        # Fix previous link
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next  # Deleting head

        # Fix next link
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev  # Deleting tail

        node.prev = node.next = None  # Clean up
        self.size -= 1
        return node.data

    def delete_head(self):
        """Remove and return the head node's data. O(1)."""
        if self.is_empty():
            raise IndexError("Delete from empty list")
        return self.delete_node(self.head)

    def delete_tail(self):
        """Remove and return the tail node's data. O(1)."""
        if self.is_empty():
            raise IndexError("Delete from empty list")
        return self.delete_node(self.tail)

    # ---------- Search & Traversal ----------

    def find(self, data):
        """Find the first node with given data. O(n)."""
        current = self.head
        while current:
            if current.data == data:
                return current
            current = current.next
        return None

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

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

    def __repr__(self):
        values = list(self.traverse_forward())
        return f"DLL({' <-> '.join(str(v) for v in values)})"

Testing the implementation

dll = DoublyLinkedList()
dll.insert_at_tail(10)
dll.insert_at_tail(20)
dll.insert_at_tail(30)
dll.insert_at_head(5)

print(dll)  # DLL(5 <-> 10 <-> 20 <-> 30)

# Insert after node with value 10
node_10 = dll.find(10)
dll.insert_after(node_10, 15)
print(dll)  # DLL(5 <-> 10 <-> 15 <-> 20 <-> 30)

# Delete from both ends
dll.delete_head()  # removes 5
dll.delete_tail()  # removes 30
print(dll)  # DLL(10 <-> 15 <-> 20)

# Traverse backward
print(list(dll.traverse_backward()))  # [20, 15, 10]

Why DLL Deletion is O(1) but SLL Deletion is O(n)

In a singly linked list, to delete a node you need its predecessor — and finding the predecessor requires traversing from the head, which is O(n).

In a doubly linked list, every node already knows its predecessor via the prev pointer. So if you have a direct reference to the node, you can unlink it in constant time:

# Singly linked list deletion — must find predecessor
def sll_delete(head, target):
    if head == target:
        return head.next
    current = head
    while current.next != target:  # O(n) search
        current = current.next
    current.next = target.next
    return head

# Doubly linked list deletion — O(1) with direct reference
def dll_delete(node):
    if node.prev:
        node.prev.next = node.next
    if node.next:
        node.next.prev = node.prev

This is exactly why data structures like LRU caches use a DLL — they need to delete arbitrary nodes in O(1).

Circular Doubly Linked List

A circular linked list connects the tail back to the head, forming a ring:

• tail.next = head
• head.prev = tail

There is no None at either end — the list loops forever.

class CircularDLL:
    def __init__(self):
        # Use a sentinel node to simplify edge cases
        self.sentinel = DLLNode(None)
        self.sentinel.next = self.sentinel
        self.sentinel.prev = self.sentinel
        self.size = 0

    def is_empty(self):
        return self.size == 0

    def insert_at_front(self, data):
        """Insert after sentinel (at the front). O(1)."""
        new_node = DLLNode(data)
        new_node.next = self.sentinel.next
        new_node.prev = self.sentinel
        self.sentinel.next.prev = new_node
        self.sentinel.next = new_node
        self.size += 1

    def insert_at_back(self, data):
        """Insert before sentinel (at the back). O(1)."""
        new_node = DLLNode(data)
        new_node.prev = self.sentinel.prev
        new_node.next = self.sentinel
        self.sentinel.prev.next = new_node
        self.sentinel.prev = new_node
        self.size += 1

    def remove(self, node):
        """Remove a non-sentinel node. O(1)."""
        if node is self.sentinel:
            raise ValueError("Cannot remove sentinel")
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None
        self.size -= 1
        return node.data

    def traverse(self):
        """Yield all values in order."""
        current = self.sentinel.next
        while current is not self.sentinel:
            yield current.data
            current = current.next

    def __repr__(self):
        values = list(self.traverse())
        if not values:
            return "CircularDLL(empty)"
        return f"CircularDLL({' -> '.join(str(v) for v in values)} -> ...)"

The sentinel trick

Using a sentinel (dummy) node eliminates all the if head is None and if tail is None edge cases. The sentinel sits between the logical “tail” and “head” of the list. Even an empty circular DLL has the sentinel pointing to itself, so insertion and deletion never need special-case code.

cdll = CircularDLL()
cdll.insert_at_front(10)
cdll.insert_at_front(20)
cdll.insert_at_back(5)
print(cdll)  # CircularDLL(20 -> 10 -> 5 -> ...)

# The list wraps around — after 5 comes 20 again
node = cdll.sentinel.next  # 20
for _ in range(7):
    if node is not cdll.sentinel:
        print(node.data, end=" ")
    node = node.next
# Output: 20 10 5 20 10 5 20

When to use Circular Linked Lists

Circular lists are useful when you need to cycle through elements repeatedly:

Use Case	Why Circular?
Music player playlist	After the last song, play the first again
Round-robin scheduling	OS gives each process a time slice, then cycles
Multiplayer game turns	After the last player, it’s player 1’s turn
Circular buffer	Producer/consumer with fixed-size wrap-around
Josephus problem	Classic elimination game in a circle

Singly vs Doubly Linked List — Trade-offs

Feature	Singly LL	Doubly LL
Memory per node	2 fields (data, next)	3 fields (prev, data, next)
Insert at head	O(1)	O(1)
Insert at tail (with tail ptr)	O(1)	O(1)
Delete head	O(1)	O(1)
Delete tail	O(n) — need predecessor	O(1) — have prev
Delete given node	O(n) — need predecessor	O(1) — have prev
Reverse traversal	O(n) — must reverse first	O(1) — walk prev
Implementation complexity	Simpler	More pointer updates

Rule of thumb: Use a DLL when you need O(1) deletion of arbitrary nodes or backward traversal. Use a singly linked list when memory matters and you only traverse forward.

Real-World Applications

Browser History (Back/Forward)

class BrowserHistory:
    """Browser back/forward using a doubly linked list."""
    def __init__(self, homepage):
        self.current = DLLNode(homepage)

    def visit(self, url):
        """Visit a new URL — clears forward history."""
        new_page = DLLNode(url)
        new_page.prev = self.current
        self.current.next = new_page
        self.current = new_page

    def back(self, steps):
        """Go back up to 'steps' pages."""
        while steps > 0 and self.current.prev:
            self.current = self.current.prev
            steps -= 1
        return self.current.data

    def forward(self, steps):
        """Go forward up to 'steps' pages."""
        while steps > 0 and self.current.next:
            self.current = self.current.next
            steps -= 1
        return self.current.data


# Usage
browser = BrowserHistory("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.visit("reddit.com")

print(browser.back(2))     # youtube.com
print(browser.forward(1))  # github.com
browser.visit("docs.python.org")  # clears reddit.com from forward
print(browser.back(1))     # github.com

Music Player (Circular Playlist)

class MusicPlayer:
    """Circular playlist with next/prev track."""
    def __init__(self):
        self.playlist = CircularDLL()
        self.current = None

    def add_song(self, title):
        self.playlist.insert_at_back(title)
        if self.current is None:
            self.current = self.playlist.sentinel.next

    def next_track(self):
        if self.playlist.is_empty():
            return None
        self.current = self.current.next
        if self.current is self.playlist.sentinel:
            self.current = self.current.next
        return self.current.data

    def prev_track(self):
        if self.playlist.is_empty():
            return None
        self.current = self.current.prev
        if self.current is self.playlist.sentinel:
            self.current = self.current.prev
        return self.current.data

    def now_playing(self):
        return self.current.data if self.current else None


player = MusicPlayer()
player.add_song("Bohemian Rhapsody")
player.add_song("Stairway to Heaven")
player.add_song("Hotel California")

print(player.now_playing())  # Bohemian Rhapsody
print(player.next_track())   # Stairway to Heaven
print(player.next_track())   # Hotel California
print(player.next_track())   # Bohemian Rhapsody (wraps around!)
print(player.prev_track())   # Hotel California

Complexity Summary

Operation	Time	Space
Insert at head/tail	O(1)	O(1)
Insert after/before node	O(1)	O(1)
Delete any node (with ref)	O(1)	O(1)
Search by value	O(n)	O(1)
Traverse (forward or back)	O(n)	O(1)
Space for n nodes	—	O(n)

Practice Problems

1. LeetCode 146 — LRU Cache: Uses a DLL + HashMap for O(1) get and put. This is the most important DLL problem.
2. LeetCode 430 — Flatten a Multilevel DLL: Flatten a DLL that has child pointers.
3. LeetCode 1472 — Design Browser History: Exactly the browser history problem above.
4. LeetCode 432 — All O’one Data Structure: Uses a DLL for O(1) min/max tracking.
5. Josephus Problem: Classic circular list elimination — every k-th person is removed until one remains.

Key Takeaways

• A DLL trades one extra pointer per node for the ability to delete any node in O(1) and traverse backward.
• Circular DLLs eliminate edge cases by connecting tail to head, making them ideal for cyclic patterns like playlists and schedulers.
• The sentinel node pattern simplifies circular DLL code by removing all null checks.
• DLLs are the backbone of LRU caches, text editors (undo/redo), and browser navigation.