Doubly Linked List

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Insert at head	O(1)
Insert at tail	O(1)
Delete a node you have a reference to	O(1)
Search / access by value	O(n)
Reverse whole list	O(n)

The Idea

A singly linked list was a one-way scavenger hunt. Each clue tells you the location of the next clue, but nothing about where you came from. When you reach node 5, you have no way back to node 4. Your only option is to start again from the head and walk forward. A doubly linked list fixes this. It gives every node a second pointer, prev, next to next. Now each clue also remembers the clue before it. So you can go back along your steps without a restart of the hunt.

This second pointer is not free. Each node now carries two addresses instead of one. So the list costs about two times the pointer memory. In exchange, you get backward traversal. You also get the real reason that doubly linked lists exist: you can delete a node that you already have a reference to in O(1), with no walk to find what points at it. The deleteValue of a singly linked list had to walk from the head to find the node before the target. That node is the only one whose next it could rewrite. Here, the target node already knows its own neighbors.

You trade memory (a second pointer for each node) for two things: a backward walk, and O(1) removal of a node that you hold. If you never need either one, the extra pointer is dead weight. This is exactly why a singly linked list is still the default choice.

Build It

Structures

structure Node:
    value
    next          // -> next Node, or NULL
    prev          // -> previous Node, or NULL

structure DoublyLinkedList:
    head          // -> first Node, or NULL if empty
    tail          // -> last Node, or NULL if empty. Keep it in sync on every insert and delete.

insertAtHead — O(1)

function insertAtHead(list, value):
    newNode = Node(value)
    newNode.next = list.head
    newNode.prev = NULL
    if list.head is not NULL:
        list.head.prev = newNode   // the old first node now points back to the new node
    list.head = newNode
    if list.tail is NULL:          // the list was empty: the new node is head AND tail
        list.tail = newNode

insertAtTail — O(1), thanks to the tail pointer

function insertAtTail(list, value):
    newNode = Node(value)
    newNode.next = NULL
    newNode.prev = list.tail
    if list.tail is not NULL:
        list.tail.next = newNode
    else:                          // the list was empty: the new node is head AND tail
        list.head = newNode
    list.tail = newNode

Remember the insertAtTail of a singly linked list. It had to walk the full list to find the last node. Here the list always keeps a hand on the last node. So an insert at the tail costs the same one-pointer rewrite as an insert at the head.

deleteNode(node) — O(1), given a direct reference

function deleteNode(list, node):
    if node.prev is not NULL:
        node.prev.next = node.next
    else:
        list.head = node.next      // the node was the head
    if node.next is not NULL:
        node.next.prev = node.prev
    else:
        list.tail = node.prev      // the node was the tail

This is the whole point of the second pointer. The deleteValue of a singly linked list is O(n), because the only way to unlink a node is to rewrite the next of whatever points at it. To find that node, you walk from the head. Here, node.prev and node.next are on the node itself. There is no search and no walk. You relink two neighbors directly.

reverse — O(n) time, O(1) space

function reverse(list):
    curr = list.head
    while curr is not NULL:
        nextNode = curr.next     // save it before you overwrite curr.next
        curr.next = curr.prev    // turn the forward arrow backward
        curr.prev = nextNode     // turn the backward arrow forward
        curr = nextNode
    oldHead = list.head
    list.head = list.tail
    list.tail = oldHead

This is the same three-pointer walk as the reverse of a singly linked list. But now there are two arrows to turn for each node instead of one. If you miss the final head/tail swap, you have correctly reversed the pointers of every node, but you still call the wrong end "head".

Know It

The rule is the same as a singly linked list. Any operation that touches only head or tail is O(1). Any operation that must walk to find a position is O(n). What is different here is which operations can skip the walk. To delete a node that you already hold used to force a search for the node before it. Now it does not, because the node carries its own neighbors. This improvement is not free. Each node here pays for two pointers instead of one. So a doubly linked list costs about two times the pointer memory of a singly linked list for the same values. Do not use it if you never need to go backward or delete by reference.

Operation	Time	Space	Why
Insert at head	O(1)	O(1)	You rewrite a few pointers around the new node and the old head. You never touch the rest of the chain.
Insert at tail	O(1)	O(1)	The tail pointer means that no walk is needed. Compare a singly linked list, where this was O(n) without a tail pointer.
Delete a node you have a reference to	O(1)	O(1)	node.prev and node.next already name the neighbors to relink, so there is no search. The delete-by-value of a singly linked list is O(n), because it must walk from the head to find the node before the target first.
Search / access by value	O(n)	O(1)	There is still no index to jump to. prev helps only after you are already on a node. It does not get you to a node faster.
Reverse whole list	O(n)	O(1)	You visit each node one time, swap its two pointers, and continue.

Break It

Empty

head and tail are both NULL

HEAD→NULL

Insert, delete, search, and reverse must all check this first and return cleanly. There is no node to dereference and nothing to relink.

Single node

head == tail, and the next and prev of that one node are both NULL

HEAD→3•→NULL

To delete the only node, you must change both head and tail, not only one. The classic bug: code sets head to NULL after the delete but leaves tail at the node that is now gone (or the reverse). The list looks empty from one end and wrong from the other end.

Broken pointer symmetry

a node's next is updated but the neighbor's prev is not updated to match, or the reverse

This is the signature doubly-linked-list bug. A singly linked list cannot have it. With one pointer for each link, there is only one thing to keep consistent. Here there are two, and they must always agree about the shape of the chain. Every next needs a prev that points back at it. If you insert or delete and fix only one direction, a forward walk can look correct while a backward walk is quietly corrupted (or the reverse). This bug can hide for a long time, because half of your code never walks that way.

Value not found

you walk off either end without reaching the target

HEAD→1•→NULL

Now there are two directions to walk off the end. A forward search must stop on a NULL next. A backward search must stop on a NULL prev. If you skip either check, a missing value becomes a crash instead of a clean "not found".

Use It

Design Linked List

Implement get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex directly on Node{value, next, prev}. This is a direct exercise in the operations above.

Medium

LRU Cache

This is the main real-world use case. Use a hash map from key to node, plus a doubly linked list for order. An access moves a node to the front in O(1). An eviction removes the tail in O(1). Both need the deleteNode trick, not a search.

Medium

Design Browser History

Back and forward are a walk along prev and next from your current position.

Medium

Design Circular Deque

This is O(1) insert and delete from both ends. It is the main benefit of a tail pointer, applied directly.

Medium

Design Circular Queue

This is the same idea as Circular Deque, in the shape of a queue. Enqueue at the tail, dequeue at the head, both O(1).

Medium

Flatten a Multilevel Doubly Linked List

This is direct work on the prev, next, and child pointers. Splice each child list in where it branches. Then keep prev and next symmetric on the way out.

Medium

Copy List with Random Pointer

This is not a doubly linked list itself, but it needs the same discipline. Copy the nodes carefully. Wire up a second kind of pointer without corruption of the first.

Medium

Palindrome Linked List

Review this from Singly Linked List. There, you had to find the middle and reverse the second half. With prev pointers, you can walk inward from both head and tail. No reversal is needed.

Easy

Reverse Linked List

Review this from Singly Linked List. It is the same one-pass walk, but now you swap both next and prev on every node, as in the reverse() pattern above.

Easy

Sort List

Use merge sort on a linked list. This connects to the merge step in Sorting Intuition, adapted to splice nodes instead of a copy into a new array.

Medium