Linked ListsLesson 4

Doubly Linked List Operations

Insert, delete, and traverse in both directions. How the extra pointer simplifies deletions but adds complexity to insertions.

What Is It?

Doubly linked list operations are similar to singly linked list operations, but every change requires updating pointers in both directions. Where a singly linked list operation might update 2 pointers, a doubly linked list operation typically updates 4.

The payoff is worth it: if you have a direct reference to any node, you can delete it in O(1) — no walking required. This is the superpower of doubly linked lists.

Here is what we will cover:

Insert at head — O(1)
Insert at tail — O(1)
Insert at position — O(n)
Delete a given node — O(1)
Delete by value — O(n)
Traverse forward and backward — O(n)

Analogy

Imagine you are arranging people in a line where each person holds the hand of the person in front and the person behind. When someone new joins the line, they grab two hands (the person ahead and the person behind), and both of those people release one hand and grab the new person's instead. When someone leaves, the people on either side simply reach across and grab each other's hands. The symmetry of two-handed connections is what makes removal so clean.

How It Works

Setup: Our Starting List

For all operations, we start with these structures:

pseudocode

structure DNode:
    data
    prev
    next
structure DoublyLinkedList:
    head = null
    tail = null
    size = 0

INSERT at Head — O(1)

Four pointer updates when the list is non-empty, two when it is empty.

pseudocode

function insertAtHead(list, value):
    newNode = new DNode(value)
    if list.head is null:
        // List is empty — new node is both head and tail
        list.head = newNode
        list.tail = newNode
    else:
        newNode.next = list.head      // 1. new node points forward to old head
        newNode.prev = null           // 2. new node has no predecessor
        list.head.prev = newNode      // 3. old head points back to new node
        list.head = newNode           // 4. update head pointer
    list.size = list.size + 1

Before:

pseudocode

null <- [20] <-> [30] -> null
         ^head    ^tail

After inserting 10 at head:

Insert at Head: Pointer Changes— Inserting 10 at the head of [20] <-> [30]

1 / 4

Before: head=[20], tail=[30]

[0]

[1]

INSERT at Tail — O(1)

Symmetric to insertAtHead, but from the other end. Notice this is O(1) — unlike a singly linked list where inserting at the tail requires walking the whole list.

pseudocode

function insertAtTail(list, value):
    newNode = new DNode(value)
    if list.tail is null:
        // List is empty
        list.head = newNode
        list.tail = newNode
    else:
        newNode.prev = list.tail      // 1. new node points back to old tail
        newNode.next = null           // 2. new node has no successor
        list.tail.next = newNode      // 3. old tail points forward to new node
        list.tail = newNode           // 4. update tail pointer
    list.size = list.size + 1

Before:

pseudocode

null <- [10] <-> [20] -> null
         ^head    ^tail

After inserting 30 at tail:

pseudocode

null <- [10] <-> [20] <-> [30] -> null
         ^head              ^tail
Pointer changes:
  [30].prev = [20]    (step 1)
  [30].next = null    (step 2)
  [20].next = [30]    (step 3)
  tail = [30]         (step 4)

INSERT at Position — O(n)

Walk to the node currently at that position, then insert the new node before it.

pseudocode

function insertAtPosition(list, value, position):
    if position equals 0:
        insertAtHead(list, value)
        return
    if position equals list.size:
        insertAtTail(list, value)
        return
    // Walk to the node at the given position
    current = list.head
    for i from 0 to position - 1:
        current = current.next
    // current is the node at 'position' — insert newNode before it
    newNode = new DNode(value)
    newNode.next = current            // 1
    newNode.prev = current.prev       // 2
    current.prev.next = newNode       // 3
    current.prev = newNode            // 4
    list.size = list.size + 1

Insert 25 at position 2:

Before:

pseudocode

null <- [10] <-> [20] <-> [30] <-> [40] -> null
  position:  0      1      2        3

After:

pseudocode

null <- [10] <-> [20] <-> [25] <-> [30] <-> [40] -> null
Pointer changes (inserting before [30]):
  [25].next = [30]       (step 1)
  [25].prev = [20]       (step 2)
  [20].next = [25]       (step 3)
  [30].prev = [25]       (step 4)

DELETE a Given Node — O(1)

This is the crown jewel of doubly linked lists. If you have a reference to the node, deletion is instant.

There are four possible cases to handle:

pseudocode

function deleteNode(list, node):
    // Case 1: node is the only node in the list
    if node.prev is null and node.next is null:
        list.head = null
        list.tail = null
    // Case 2: node is the head
    else if node.prev is null:
        list.head = node.next
        node.next.prev = null
    // Case 3: node is the tail
    else if node.next is null:
        list.tail = node.prev
        node.prev.next = null
    // Case 4: node is in the middle
    else:
        node.prev.next = node.next    // bridge forward
        node.next.prev = node.prev    // bridge backward
    list.size = list.size - 1

Delete node [20] (middle case):

pseudocode

Before: null <- [10] <-> [20] <-> [30] -> null
Pointer changes:
  [10].next = [30]    (node.prev.next = node.next)
  [30].prev = [10]    (node.next.prev = node.prev)
After: null <- [10] <-> [30] -> null

Delete node [10] (head case):

pseudocode

Before: null <- [10] <-> [20] <-> [30] -> null
                 ^head
Pointer changes:
  head = [20]         (list.head = node.next)
  [20].prev = null    (node.next.prev = null)
After: null <- [20] <-> [30] -> null
                ^head

DELETE by Value — O(n)

When you do not have a node reference, search for the value first, then delete.

pseudocode

function deleteByValue(list, target):
    current = list.head
    while current is not null:
        if current.data equals target:
            deleteNode(list, current)
            return true
        current = current.next
    return false

The search is O(n), but the actual deletion is O(1) once the node is found.

TRAVERSE Forward and Backward

pseudocode

function traverseForward(list):
    current = list.head
    while current is not null:
        process(current.data)
        current = current.next
function traverseBackward(list):
    current = list.tail
    while current is not null:
        process(current.data)
        current = current.prev

Both are O(n). Going backward is something a singly linked list cannot do at all.

Operation Complexity Summary

Insert at head—

O(1)

Insert at tail— tail pointer

O(1)

Insert at position— must traverse

O(n)

Delete given node— the DLL superpower

O(1)

Delete by value— must search first

O(n)

Search—

O(n)

Traverse— either direction

O(n)

Examples

Example: Building and Manipulating a List

Build and Manipulate a DLL— Step-by-step list state after each operation

1 / 6

insertAtTail(10)

[0]

Example: Using deleteNode with a Direct Reference

This pattern is common in interview problems and real applications:

pseudocode

// Store node references in a hash map for fast lookup
nodeMap = {}
// When inserting
node = new DNode(42)
insertAtTail(list, node)
nodeMap[42] = node
// When we need to remove 42 later
deleteNode(list, nodeMap[42])    // O(1) — no walking!
remove 42 from nodeMap

Common Mistakes

1. Updating only one direction. The most common bug. If you update A.next = C but forget C.prev = A, forward traversal works but backward traversal is broken. Always update both.

2. Missing cases in deleteNode. There are four distinct situations (only node, head, tail, middle). Skipping any one leads to null pointer crashes.

3. Wrong order of pointer updates. When inserting at a position, if you update current.prev.next = newNode before setting newNode.prev = current.prev, you lose the reference you need. Always set the new node's pointers first, then update the neighbors.

4. Not updating head or tail. Inserting at the front must update head. Inserting at the back must update tail. Deleting the head must update head. Deleting the tail must update tail. Deleting the only node must null out both.

5. Confusing position counting. Position 0 is the head. To reach the node at position k, you advance k times from the head.

Best Practices

Always update both pointers. When in doubt, ask yourself after every operation: "did I update both the forward AND backward links for every pair of neighbors I touched?"

Save references before rewiring. When inserting at a position, save current.prev in a variable before you start changing pointers. Changing one pointer can make another node unreachable.

Test all four delete cases. Write tests for: deleting the only node, deleting the head, deleting the tail, and deleting a middle node. These four cases cover every possible situation.

Combine with a hash map for O(1) everything. A doubly linked list paired with a hash map (key to node reference) gives you O(1) lookup, O(1) deletion, and O(1) move-to-front. This is how LRU caches work in real code.

Doubly Linked Lists How Stacks Work