Doubly Linked List

What Is a Doubly Linked List?

A doubly linked list is a linked list where each node holds three fields instead of two: a pointer to the previous node, the data, and a pointer to the next node. This bidirectional linking allows traversal in both directions — forward from head to tail and backward from tail to head.

Doubly linked list: null ← 10 ↔ 20 ↔ 30 ↔ 40 → null

null ←─ ┌──────┬──────┬──────┐ ↔ ┌──────┬──────┬──────┐ ↔ ┌──────┬──────┬──────┐ ↔ ┌──────┬──────┬──────┐ ─→ null
        │ null │  10  │  ●───┼──▶│  ●   │  20  │  ●───┼──▶│  ●   │  30  │  ●───┼──▶│  ●   │  40  │ null │
        └──────┴──────┴──────┘   └──┼───┴──────┴──────┘   └──┼───┴──────┴──────┘   └──┼───┴──────┴──────┘
  head     prev  data  next    ◀────┘ prev  data  next    ◀────┘ prev  data  next    ◀────┘ prev  data  next

Each node's prev points back to the previous node. The head's prev is null (nothing before it). The tail's next is null (nothing after it).

Singly vs Doubly — The Key Difference

Singly Linked List node:       Doubly Linked List node:
  ┌──────┬──────┐                ┌──────┬──────┬──────┐
  │ data │ next │                │ prev │ data │ next │
  └──────┴──────┘                └──────┴──────┴──────┘

  Traverse: forward only          Traverse: forward AND backward
  Delete at end: O(n)             Delete at known node: O(1)
  Extra memory: 1 pointer/node    Extra memory: 2 pointers/node

The prev pointer costs one extra memory reference per node but enables:

• ›Backward traversal without a second pass
• ›O(1) deletion of a node when you already have a pointer to it
• ›Inserting before a given node without tracking a separate prev variable

Node and LinkedList Structure

Operation 1: Traverse — Forward and Backward

Because each node stores both prev and next, you can traverse the list in either direction.

Output (list: 10 ↔ 20 ↔ 30):
Forward:  10 → 20 → 30 → null
Backward: null ← 30 ← 20 ← 10 ←

Operation 2: Length — Count All Nodes

Output (list: 10 ↔ 20 ↔ 30 ↔ 40):
4

Operation 3: Search — Find an Element

Output:
searchElement(20) → true
searchElement(99) → false

Operation 4: Insert at Beginning — O(1)

Create a new node. Point its next to the current head. Update the current head's prev to the new node. Make the new node the new head.

Before: null ← 20 ↔ 30 → null
Insert 10 at beginning:

Step 1: newNode(10), prev=null, next=null
Step 2: newNode.next = head (Node 20)
Step 3: head.prev    = newNode  (Node 20 now points back to 10)
Step 4: head         = newNode  (10 is the new head)

After: null ← 10 ↔ 20 ↔ 30 → null

Dry Run: insertAtBeg on empty list, then insert 20, then 10

Start: head = null

insertAtBeg(30):
  head == null → head = Node(30)
  List: null ← 30 → null

insertAtBeg(20):
  newNode = Node(20)
  newNode.next = head (Node 30)
  head.prev    = newNode (Node 30.prev = Node 20)
  head         = newNode (Node 20 is new head)
  List: null ← 20 ↔ 30 → null

insertAtBeg(10):
  newNode = Node(10)
  newNode.next = head (Node 20)
  head.prev    = newNode (Node 20.prev = Node 10)
  head         = newNode
  List: null ← 10 ↔ 20 ↔ 30 → null

Operation 5: Insert at End — O(n)

Traverse to the last node, attach the new node after it, set the new node's prev to the last node.

Dry Run: Insert 40 at End of [10 ↔ 20 ↔ 30]

newNode = Node(40)
temp = head = Node(10)

Walk to last node:
  temp=Node(10): next=Node(20) ≠ null → temp=Node(20)
  temp=Node(20): next=Node(30) ≠ null → temp=Node(30)
  temp=Node(30): next=null → STOP

Attach:
  temp.next    = newNode   → Node(30).next = Node(40)
  newNode.prev = temp      → Node(40).prev = Node(30)

Result: null ← 10 ↔ 20 ↔ 30 ↔ 40 → null

Two pointer updates — one forward, one backward link.

Operation 6: Insert at Middle (After a Given Value)

Find the node with value aft, then insert the new node immediately after it. Update four pointers: two from the new node, two from neighbors.

Dry Run: Insert 25 After 20 in [10 ↔ 20 ↔ 30]

newNode = Node(25)
Find node with data=20: temp = Node(20)

Four pointer updates:
  1. newNode.prev = temp         → Node(25).prev = Node(20)
  2. newNode.next = temp.next    → Node(25).next = Node(30)
  3. temp.next.prev = newNode    → Node(30).prev = Node(25)
  4. temp.next = newNode         → Node(20).next = Node(25)

Before: null ← 10 ↔ 20 ↔ 30 → null
After:  null ← 10 ↔ 20 ↔ 25 ↔ 30 → null

Order matters for step 3:
  temp.next is still Node(30) when we update Node(30).prev.
  If we did step 4 first, temp.next would be newNode — updating
  newNode.prev to itself, not Node(30).prev.
  Always update the NEIGHBOR pointers before redirecting temp.next.

Operation 7: Insert at Middle (Before a Given Value)

Find the node with value prev, then insert the new node immediately before it using both prev and next pointers.

Dry Run: Insert 15 Before 20 in [10 ↔ 20 ↔ 30]

newNode = Node(15)
Find node with data=20: temp = Node(20)

Four pointer updates:
  1. newNode.prev    = temp.prev    → Node(15).prev = Node(10)
  2. newNode.next    = temp         → Node(15).next = Node(20)
  3. temp.prev.next  = newNode      → Node(10).next = Node(15)
  4. temp.prev       = newNode      → Node(20).prev = Node(15)

Before: null ← 10 ↔ 20 ↔ 30 → null
After:  null ← 10 ↔ 15 ↔ 20 ↔ 30 → null

The key advantage over singly linked:
  We can insert before temp using temp.prev — no need for
  a separate trailing pointer variable.

Operation 8: Delete from Beginning — O(1)

Move head forward. Update the new head's prev to null.

Before: null ← 10 ↔ 20 ↔ 30 → null
After deleteAtBeg():
  head = Node(20)
  head.prev = null
Result: null ← 20 ↔ 30 → null

Operation 9: Delete from End — O(n)

Traverse to the last node, then set the second-to-last node's next to null.

Dry Run: Delete from End of [10 ↔ 20 ↔ 30]

temp = head = Node(10)

Walk to last node:
  temp=Node(10): next=Node(20) ≠ null → temp=Node(20)
  temp=Node(20): next=Node(30) ≠ null → temp=Node(30)
  temp=Node(30): next=null → STOP

Detach: temp.prev.next = null
  Node(30).prev = Node(20)
  Node(20).next = null

Result: null ← 10 ↔ 20 → null  (Node(30) removed)

Advantage over singly: no need for a trailing temp1 variable.
  Node(30).prev already gives us Node(20) directly.

Operation 10: Delete from Middle — Remove by Value

Find the target node using prev and next to bypass it cleanly. The prev pointer makes this cleaner than singly linked — no trailing second pointer needed.

Dry Run: Delete 20 from [10 ↔ 20 ↔ 30]

Find node with data=20: temp = Node(20)

Bypass temp:
  temp.prev != null (it's Node(10)):
    temp.prev.next = temp.next → Node(10).next = Node(30)
  temp.next != null (it's Node(30)):
    temp.next.prev = temp.prev → Node(30).prev = Node(10)

Result: null ← 10 ↔ 30 → null

Advantage over singly: both pointers are available on temp itself.
  In singly, we needed a trailing `prev` variable.
  In doubly, temp.prev gives us the predecessor directly.

Complete Working Example

Output:
After build:
10 → 20 → 30 → null
null ← 30 ← 20 ← 10 ←
10 → 20 → 30 → 40 → null
10 → 20 → 25 → 30 → 40 → null
10 → 15 → 20 → 25 → 30 → 40 → null
15 → 20 → 25 → 30 → 40 → null
15 → 20 → 30 → 40 → null
15 → 20 → 30 → null
Search 20: true
Search 99: false
Length:    3

Time & Space Complexity

Time Complexity

Space Complexity

Common Mistakes Beginners Make

Forgetting to update the prev pointer on insertAtBeg. After setting newNode.next = head, you must also set head.prev = newNode before moving head. Skipping this leaves the old head's prev as null instead of pointing back to the new head — breaking backward traversal.

Wrong order in insertAtMidAft. When inserting after temp, update temp.next.prev = newNode BEFORE setting temp.next = newNode. After temp.next = newNode, the expression temp.next refers to newNode, not the old successor — you would set newNode.prev = newNode instead.

Not handling temp.prev == null in deleteAtMid. If the node to delete is the head, temp.prev is null and temp.prev.next = ... causes a NullPointerException. Always check: if temp.prev != null, update the predecessor; otherwise, update head.

Not setting the new head's prev to null in deleteAtBeg. After head = head.next, the new head still has its old prev pointing to the deleted node — creating a dangling reference. Always set head.prev = null after moving head forward.

Using the wrong loop condition in insertAtMidBeg. The original docx uses temp.next != null && temp.data != prev — this stops one node early if the target is the tail. Use temp != null && temp.data != prev to search correctly to any position.

Interview Questions

Q: What is the main advantage of a doubly linked list over a singly linked list?

Bidirectional traversal and O(1) deletion at a known node. In a singly linked list, deleting a node requires a trailing prev pointer because you cannot go backward. In a doubly linked list, temp.prev is always available on the node itself — deletion at a known position needs only two pointer updates without any additional traversal. With a maintained tail pointer, deletion at the tail is also O(1) instead of O(n).

Q: How many pointer updates are needed to insert a node after a given node in a doubly linked list?

Four. (1) newNode.prev = temp, (2) newNode.next = temp.next, (3) temp.next.prev = newNode (if the successor exists), (4) temp.next = newNode. Step 3 must happen before step 4 — after step 4, temp.next refers to newNode, not the original successor.

Q: Why does deleteAtEnd use temp.prev.next = null instead of a second trailing pointer?

Because the doubly linked list's prev pointer eliminates the need for a trailing variable. When temp reaches the last node, temp.prev directly gives the second-to-last node. Setting temp.prev.next = null detaches the last node cleanly. In a singly linked list, you need a temp1 variable trailing one step behind because there is no way to reach the predecessor from the current node.

FAQs

Does every doubly linked list operation require four pointer updates?

Not always. Insert at beginning requires three (newNode.next, head.prev, head). Delete at beginning requires two (head = head.next, head.prev = null). Only mid-insert and mid-delete require four because they update both neighbors and the new/removed node. The pattern: the more central a position, the more pointers must be updated.

When would you maintain a separate tail pointer in a doubly linked list?

When insertAtEnd and deleteAtEnd need to be O(1). Without a tail pointer, both require O(n) traversal. With a tail pointer, insertAtEnd attaches the new node directly to tail and updates tail in O(1). deleteAtEnd moves tail to tail.prev and sets tail.next = null in O(1). LRU cache implementations always maintain both head and tail for O(1) access at both ends.

Can you delete a node in a doubly linked list without knowing the head?

Yes — if you have a direct pointer to the node AND it is not the head or tail. Set node.prev.next = node.next and node.next.prev = node.prev. This is why doubly linked lists are used in LRU caches: you can move a node to the front with only a reference to that node — no traversal needed.

Quick Quiz

Question 1: Inserting at the beginning of a doubly linked list requires how many pointer updates?

• ›A) 1
• ›B) 2
• ›C) 3
• ›D) 4

Answer: C) 3. newNode.next = head, head.prev = newNode, then head = newNode. Three assignments. (For an empty list, just head = newNode — one assignment.)

Question 2: In deleteAtEnd, after traversing to the last node temp, the correct detachment is:

• ›A) temp = null
• ›B) temp.next = null
• ›C) temp.prev.next = null
• ›D) head = temp.prev

Answer: C) temp.prev.next = null. temp is the last node. temp.prev is the second-to-last. Setting temp.prev.next = null makes the second-to-last the new tail. Setting temp = null only removes the local variable reference — the list still points to temp. Option D would make the second-to-last the head, losing everything except one node.

Question 3: When inserting 25 after node 20 in [10 ↔ 20 ↔ 30], which pointer must be updated BEFORE redirecting temp.next?

• ›A) newNode.prev
• ›B) newNode.next
• ›C) temp.next.prev (setting Node(30).prev = newNode)
• ›D) temp.prev

Answer: C) temp.next.prev. After temp.next = newNode, temp.next refers to newNode — so temp.next.prev = newNode would set newNode.prev = newNode (self-referential). Node(30).prev must be updated while temp.next still refers to Node(30).

Question 4: What is the key advantage when deleting a middle node from a doubly linked list compared to a singly linked list?

• ›A) Doubly linked deletion is O(1) regardless of position
• ›B) No need for a trailing prev variable — temp.prev gives the predecessor directly
• ›C) Doubly linked lists do not need to check for empty lists
• ›D) The node's memory is freed automatically

Answer: B) No trailing prev variable needed. In a singly linked list, to delete node curr you need a pointer to its predecessor — requiring a separate prev variable updated at every step. In a doubly linked list, curr.prev is directly available on the node itself. The deletion requires only two assignments: curr.prev.next = curr.next and curr.next.prev = curr.prev.

Summary

A doubly linked list extends the singly linked list by adding a prev pointer to each node, enabling bidirectional traversal and cleaner deletion at known positions.

The ten core operations and their key mechanics:

• ›Traverse forward — O(n) — same as singly: temp = temp.next until null
• ›Traverse backward — O(n) — reach tail first, then temp = temp.prev until null
• ›Length — O(n) — count during forward traversal
• ›Search — O(n) — scan forward, return true on match
• ›Insert at beginning — O(1) — three pointer updates: newNode.next, head.prev, head
• ›Insert at end — O(n) — walk to tail, two pointer updates: temp.next, newNode.prev
• ›Insert after given node — O(n) — four updates: update successor's prev BEFORE redirecting temp.next
• ›Insert before given node — O(n) — four updates: use temp.prev to reach predecessor directly
• ›Delete from beginning — O(1) — head = head.next, new head's prev = null
• ›Delete from end — O(n) — walk to tail, use temp.prev.next = null — no trailing variable needed
• ›Delete from middle — O(n) — bypass with temp.prev.next and temp.next.prev — handles head/tail as special cases

In the next topic, you will explore the Circular Linked List — where the tail's next points back to the head, forming a continuous loop with no null terminator.