Why Doubly Linked List Over Singly Linked List in DSA Go - Why This Pattern

Mental Model

A doubly linked list lets you move forward and backward easily, unlike a singly linked list which only moves forward.

Analogy: Think of a train with cars connected both ways, so you can walk from front to back or back to front. A singly linked list is like a one-way street where you can only go forward.

Singly Linked List:
head -> [1] -> [2] -> [3] -> null

Doubly Linked List:
null ← [1] ↔ [2] ↔ [3] -> null

Dry Run Walkthrough

Input: list: 1->2->3, delete node 2

Goal: Show how deleting a middle node is easier in doubly linked list than singly linked list

Step 1: In singly linked list, find node before 2 (node 1)

1 -> [curr->2] -> 3 -> null

Why: We need the previous node to remove node 2

Step 2: Change node 1's next to node 3, skipping node 2

1 -> 3 -> null

Why: This removes node 2 by skipping it

Step 3: In doubly linked list, directly access node 2

null ← 1 ↔ [curr->2] ↔ 3 -> null

Why: We can move backward and forward easily

Step 4: Change node 1's next to node 3 and node 3's prev to node 1

null ← 1 ↔ 3 -> null

Why: Both links update to remove node 2 cleanly

Result:

Singly linked list after deletion: 1 -> 3 -> null
Doubly linked list after deletion: null ← 1 ↔ 3 -> null

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	val  int
	next *Node
	prev *Node
}

// Delete node with value 2 from singly linked list
func deleteSingly(head *Node, val int) *Node {
	if head == nil {
		return nil
	}
	if head.val == val {
		return head.next
	}
	curr := head
	// find node before target
	for curr.next != nil && curr.next.val != val {
		curr = curr.next
	}
	if curr.next != nil {
		curr.next = curr.next.next
	}
	return head
}

// Delete node with value 2 from doubly linked list
func deleteDoubly(head *Node, val int) *Node {
	curr := head
	// find target node
	for curr != nil && curr.val != val {
		curr = curr.next
	}
	if curr == nil {
		return head
	}
	// update prev's next
	if curr.prev != nil {
		curr.prev.next = curr.next
	} else {
		head = curr.next
	}
	// update next's prev
	if curr.next != nil {
		curr.next.prev = curr.prev
	}
	return head
}

// Print singly linked list
func printSingly(head *Node) {
	curr := head
	for curr != nil {
		fmt.Printf("%d", curr.val)
		if curr.next != nil {
			fmt.Print(" -> ")
		}
		curr = curr.next
	}
	fmt.Println(" -> null")
}

// Print doubly linked list forward
func printDoubly(head *Node) {
	curr := head
	fmt.Print("null ← ")
	for curr != nil {
		fmt.Printf("%d", curr.val)
		if curr.next != nil {
			fmt.Print(" ↔ ")
		}
		curr = curr.next
	}
	fmt.Println(" -> null")
}

func main() {
	// Singly linked list: 1 -> 2 -> 3 -> null
	headS := &Node{val: 1, next: &Node{val: 2, next: &Node{val: 3}}}
	// Delete 2
	headS = deleteSingly(headS, 2)
	printSingly(headS)

	// Doubly linked list: null ← 1 ↔ 2 ↔ 3 -> null
	headD := &Node{val: 1}
	node2 := &Node{val: 2}
	node3 := &Node{val: 3}
	headD.next = node2
	node2.prev = headD
	node2.next = node3
	node3.prev = node2
	// Delete 2
	headD = deleteDoubly(headD, 2)
	printDoubly(headD)
}

for curr.next != nil && curr.next.val != val { curr = curr.next }

advance curr to node before target to update next pointer

curr.next = curr.next.next

skip target node by linking previous node to next of target

for curr != nil && curr.val != val { curr = curr.next }

find target node directly in doubly linked list

if curr.prev != nil { curr.prev.next = curr.next } else { head = curr.next }

update previous node's next or head if target is first node

if curr.next != nil { curr.next.prev = curr.prev }

update next node's prev to skip target node

Output

1 -> 3 -> null

null ← 1 ↔ 3 -> null

Complexity Analysis

Time: O(n) because we may need to traverse the list to find the node to delete

Space: O(1) because deletion uses constant extra space

vs Alternative: Doubly linked list allows direct backward access to previous node, making deletion easier and cleaner compared to singly linked list which requires traversal to find previous node

Edge Cases

empty list

function returns nil without error

DSA Go

if head == nil {
	return nil
}

deleting head node

head pointer updates to next node correctly

DSA Go

if head.val == val {
	return head.next
}

node to delete not found

list remains unchanged

DSA Go

if curr == nil {
	return head
}

When to Use This Pattern

When you need to delete or insert nodes efficiently from both ends or middle, and want easy backward traversal, reach for doubly linked list because it stores previous pointers.

Common Mistakes

Mistake: In singly linked list deletion, forgetting to find the previous node before the target
Fix: Always traverse to the node before the one to delete to update its next pointer

Mistake: In doubly linked list deletion, forgetting to update the prev pointer of the next node
Fix: After removing target, update next node's prev to target's prev to maintain links

Summary

It shows why doubly linked lists let you move backward and forward, making some operations easier.

Use doubly linked lists when you need to delete or insert nodes from both directions efficiently.

The key insight is that storing a previous pointer lets you avoid searching for the previous node.

Practice

1. Why might you choose a doubly linked list over a singly linked list in a program?

easy

A. Because it uses less memory per node

B. Because it only stores one pointer per node

C. Because it is simpler to implement

D. Because it allows traversal in both directions easily

Solution

1. Step 1: Understand traversal capabilities

   A doubly linked list stores two pointers per node: one to the next node and one to the previous node, allowing movement forward and backward.

2. Step 2: Compare with singly linked list

   A singly linked list stores only one pointer to the next node, so it can only be traversed forward easily.

3. Final Answer:

   Because it allows traversal in both directions easily -> Option D

4. Quick Check:

   Traversal both ways = B [OK]

Hint: Doubly means two directions for traversal [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Assuming singly linked lists allow backward traversal
• Confusing simplicity of implementation

2. Which of the following is the correct way to declare a node struct for a doubly linked list in Go?

easy

A. type Node struct { data int; prev *Node; next *Node }

B. type Node struct { data int; next *Node }

C. type Node struct { data int; prev int; next int }

D. type Node struct { data int; next int }

Solution

1. Step 1: Identify required pointers for doubly linked list node

   A doubly linked list node must have pointers to both previous and next nodes, so it needs two pointers of type *Node.

2. Step 2: Check each option's struct fields

   type Node struct { data int; prev *Node; next *Node } correctly declares both prev *Node and next *Node. Others miss one or use wrong types.

3. Final Answer:

   type Node struct { data int; prev *Node; next *Node } -> Option A

4. Quick Check:

   Two pointers prev and next = A [OK]

Hint: Doubly linked node needs prev and next pointers [OK]

Common Mistakes:

• Using int instead of pointer for prev/next
• Missing prev pointer in struct
• Confusing singly linked list node with doubly linked

3. What will be the output of the following Go code snippet that uses a doubly linked list?

type Node struct {
    data int
    prev *Node
    next *Node
}

func printForward(head *Node) {
    for current := head; current != nil; current = current.next {
        fmt.Print(current.data, " ")
    }
}

func printBackward(tail *Node) {
    for current := tail; current != nil; current = current.prev {
        fmt.Print(current.data, " ")
    }
}

func main() {
    n1 := &Node{data: 1}
    n2 := &Node{data: 2}
    n3 := &Node{data: 3}

    n1.next = n2
    n2.prev = n1
    n2.next = n3
    n3.prev = n2

    printForward(n1)
    fmt.Println()
    printBackward(n3)
}

medium

A. 1 2 3 \n 1 2 3

B. 3 2 1 \n 1 2 3

C. 1 2 3 \n 3 2 1

D. 3 2 1 \n 3 2 1

Solution

1. Step 1: Trace printForward function

   Starting at n1 (data=1), it prints 1, then moves to n2 (2), then n3 (3), then nil. Output: "1 2 3 "

2. Step 2: Trace printBackward function

   Starting at n3 (3), it prints 3, then moves to n2 (2), then n1 (1), then nil. Output: "3 2 1 "

3. Final Answer:

   1 2 3 \n 3 2 1 -> Option C

4. Quick Check:

   Forward then backward print = A [OK]

Hint: Forward prints from head, backward from tail [OK]

Common Mistakes:

• Confusing prev and next pointers in loops
• Printing backward list in forward order
• Missing nil check causing runtime error

4. The following Go code tries to insert a new node after a given node in a doubly linked list. What is the bug?

func insertAfter(node *Node, newNode *Node) {
    newNode.next = node.next
    node.next = newNode
    newNode.prev = node
}

medium

A. It does not set node.next correctly

B. It does not update the prev pointer of the node after newNode

C. It does not set newNode.prev correctly

D. It does not set newNode.next correctly

Solution

1. Step 1: Analyze pointer updates in insertAfter

   The code sets newNode.next to node.next and newNode.prev to node, and updates node.next to newNode.

2. Step 2: Identify missing pointer update

   If node.next was not nil, the previous pointer of node.next (the node after newNode) should be updated to newNode. This step is missing.

3. Final Answer:

   It does not update the prev pointer of the node after newNode -> Option B

4. Quick Check:

   Missing prev update of next node = C [OK]

Hint: Always update prev pointer of next node after insertion [OK]

Common Mistakes:

• Forgetting to update next node's prev pointer
• Confusing prev and next pointers
• Assuming node.next is always nil

5. You want to implement a feature that requires frequent backward traversal and deletion of nodes from the middle of a list. Why is a doubly linked list better than a singly linked list for this task?

hard

A. Because doubly linked lists allow backward traversal and easy access to previous nodes for deletion

B. Because singly linked lists use less memory and are faster for deletion

C. Because doubly linked lists do not need pointers to previous nodes

D. Because singly linked lists allow backward traversal without extra pointers

Solution

1. Step 1: Understand backward traversal requirement

   Backward traversal means moving from a node to its previous node, which singly linked lists cannot do easily because they only have next pointers.

2. Step 2: Understand deletion from middle nodes

   To delete a node, you need to update the previous node's next pointer. Doubly linked lists have direct access to previous nodes, making deletion easier and efficient.

3. Final Answer:

   Because doubly linked lists allow backward traversal and easy access to previous nodes for deletion -> Option A

4. Quick Check:

   Backward traversal and deletion ease = D [OK]

Hint: Backward traversal needs prev pointers for easy deletion [OK]

Common Mistakes:

• Thinking singly linked lists can traverse backward easily
• Ignoring need to update previous node on deletion
• Assuming doubly linked lists use less memory