Doubly Linked List Visualizer

How it works

1. If the index is 0, insert at the head: new.next = head, head.prev = new, head = new.
2. Otherwise walk curr from the head to the node at index i − 1.
3. Point the new node at its neighbours first: new.next = curr.next and new.prev = curr.
4. If a node follows curr, repoint its back link: curr.next.prev = new.
5. Link it in from the front last: curr.next = new. If curr was the tail, the new node becomes the tail.

Why add a prev pointer?

In a singly linked list every operation that changes the list needs the node before the one you care about. Deleting node X means rewriting its predecessor's next, and X has no idea who that is — so you walk from the head to find it. The same problem makes "delete the tail" O(n) even when you keep a tail pointer: after removing the last node you need the new last node, and only a walk can find it.

A prev pointer removes that walk. Given any node, its predecessor is one field away, so unlinking it takes a constant number of pointer writes. Paired with a tail pointer next to head — which doubly linked lists keep as standard — both ends are one step away: appending is new.prev = tail, tail.next = new, tail = new, with no walk at all. That is why doubly linked lists sit underneath LRU caches, deques and most general-purpose list types in standard libraries.

Worked example: insert 99 at index 2

This page opens with 12 ⇄ 7 ⇄ 33 ⇄ 5 ⇄ 21 ⇄ 48, with head and tail pointers, and this exact insert ready to play. Index 2 means the new node goes between 7 (index 1) and 33, so curr stops on 7 after one step. Then four writes:

• new.next = curr.next → 99 points forward to 33.
• new.prev = curr → 99 points back to 7.
• curr.next.prev = new → 33's back pointer now aims at 99.
• curr.next = new → 7's forward pointer now aims at 99.

The result is 12 ⇄ 7 ⇄ 99 ⇄ 33 ⇄ 5 ⇄ 21 ⇄ 48. The first two writes only touch the new node, so they are always safe. The order of the last two matters: set curr.next = new first and the expression curr.next.prev then refers to 99 itself, so 33 keeps pointing back at 7 — a list that reads correctly forwards and wrongly backwards. It is the most common doubly-linked-list bug, and it hides until someone walks the list in reverse.

Deleting a node in O(1)

To remove node x, connect its two neighbours to each other and drop it:

• x.prev.next = x.next (or head = x.next if x was the head)
• x.next.prev = x.prev (or tail = x.prev if x was the tail)

No search for the predecessor is needed, so deletion is O(1) once you hold the node. Deleting the tail shows the difference best: tail = tail.prev, then tail.next = NULL — two writes, where a singly linked list must walk n − 1 nodes. Deleting by index or by value is still O(n), but only because of the search; the unlinking itself is constant time.

Singly vs doubly linked list

• Memory: a doubly linked node carries one extra pointer — 8 more bytes per node on a 64-bit machine, before allocator overhead.
• Traversal: singly is forward-only; doubly walks both ways, so iterating from the tail or stepping back from a cursor is free.
• Insert: 2 pointer writes vs 4, and more links to keep consistent.
• Delete a node you hold, or the tail: O(n) vs O(1).
• Reverse: O(n) for both; in a doubly linked list each node simply swaps its next and prev.

If you only push and pop at the front, or append at the back, a singly linked list does the job with less memory. As soon as you remove nodes from the middle or need the previous element, the second pointer pays for itself.

Where doubly linked lists are used

• LRU caches: a hash map finds the node for a key in O(1), and the doubly linked list keeps entries in recency order, so moving an entry to the front and evicting from the back are both O(1). It is a classic design interview question.
• Standard libraries: Java's LinkedList and C++'s std::list are doubly linked, and Java's LinkedHashMap threads a doubly linked list through its entries to remember insertion or access order.
• Deques: a double-ended queue needs O(1) work at both ends, which a doubly linked list provides directly.
• Operating systems: the Linux kernel's list_head is a circular doubly linked list embedded inside the structures it links.

Common mistakes

• Updating curr.next before curr.next.prev during an insert (see the worked example).
• Forgetting the prev side altogether — the list still prints correctly forwards, so the bug stays hidden until someone walks backwards.
• Mishandling the ends: inserting at index 0 must update head and the old head's prev; inserting after the tail must update tail and must not touch curr.next.prev, because curr.next is NULL.
• Leaving the new head's prev or the new tail's next pointing at a node that was just deleted.

Time and space complexity

Doubly Linked List in Python

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


class LinkedList:
    def __init__(self):
        self.head = None  # first node
        self.tail = None  # last node

    def insert_at_head(self, value):
        new_node = Node(value)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node
        if self.tail is None:
            self.tail = new_node

    def insert_at_tail(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = self.tail = new_node
            return
        new_node.prev = self.tail  # O(1)
        self.tail.next = new_node
        self.tail = new_node

    def insert_at(self, index, value):
        # assumes 0 <= index <= size
        if index == 0:
            return self.insert_at_head(value)
        curr = self.head
        for i in range(1, index):  # i = 1 .. index-1
            curr = curr.next
        new_node = Node(value)
        new_node.next = curr.next  # 1st
        new_node.prev = curr
        if curr.next is not None:
            curr.next.prev = new_node
        curr.next = new_node       # 2nd
        if curr is self.tail:
            self.tail = new_node

    def delete_head(self):
        if self.head is None:
            raise IndexError("delete from empty list")
        temp = self.head
        self.head = self.head.next
        if self.head is not None:
            self.head.prev = None
        if self.head is None:
            self.tail = None
        del temp  # free(temp): the GC reclaims it

    def delete_tail(self):
        if self.head is None:
            raise IndexError("delete from empty list")
        temp = self.tail  # O(1)
        if temp.prev is None:
            self.head = self.tail = None
        else:
            self.tail = temp.prev
            self.tail.next = None
        del temp  # free(temp): the GC reclaims it

    def delete_at(self, index):
        # assumes 0 <= index < size
        if index == 0:
            return self.delete_head()
        curr = self.head
        for i in range(1, index + 1):  # i = 1 .. index
            curr = curr.next
        curr.prev.next = curr.next
        if curr.next is not None:
            curr.next.prev = curr.prev
        else:
            self.tail = curr.prev
        del curr  # free(curr): the GC reclaims it

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Linked List VisualizerInteractive linked list visualizer: watch every pointer change as you insert, delete, search and reverse singly, doubly and circular lists, with code and costs.
• Circular Linked List VisualizerCircular linked list visualizer: the last node points back to the head. See O(1) insert at both ends with a tail pointer, safe traversal and real-world uses.
• Reverse a Linked List — Step by StepReverse a linked list in place with three pointers. Watch every arrow flip step by step and compare iterative vs recursive code — O(n) time, O(1) space.
• Deque VisualizerDeque visualizer: push and pop at both the front and back of a double-ended queue on a circular array, each in O(1), and see how it acts as a stack or a queue.