Why Doubly Linked List Over Singly Linked List in DSA Go - Why It Works

Concept Flow - Why Doubly Linked List Over Singly Linked List

Start with Singly Linked List

↓

Can only move forward

↓

Operations like backward traversal or easy deletion

↓

Hard or inefficient

↓

Use Doubly Linked List

↓

Can move forward and backward

↓

Easy backward traversal and deletion

↓

More memory used but more flexible

Shows why singly linked lists limit movement to forward only, making some operations hard, while doubly linked lists allow easy forward and backward movement for more flexibility.

Execution Sample

DSA Go

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

// Singly linked list node has only 'next'
// Doubly linked list node has 'next' and 'prev'

Defines nodes for singly and doubly linked lists showing the extra 'prev' pointer in doubly linked lists.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create singly linked list with nodes 1 -> 2 -> 3	1 -> 2 -> 3	head points to 1, next pointers set	1 -> 2 -> 3 (only next pointers, no prev)
2	Try backward traversal from node 3	1 -> 2 -> 3	No prev pointers, cannot move backward	Traversal stuck at 3, no way back
3	Create doubly linked list with nodes 1 <-> 2 <-> 3	1 <-> 2 <-> 3	head points to 1, next and prev pointers set	1 <-> 2 <-> 3 (both next and prev pointers)
4	Backward traversal from node 3 to 1	1 <-> 2 <-> 3	Use prev pointers to move 3 -> 2 -> 1	Traversal possible backward: 3 -> 2 -> 1
5	Delete node 2 in singly linked list	1 -> 2 -> 3	Need to find node 1 to change next pointer to 3	Must traverse from head to update pointers
6	Delete node 2 in doubly linked list	1 <-> 2 <-> 3	Update 1.next to 3 and 3.prev to 1 directly	Deletion done easily using prev and next pointers
7	End	Final lists after operations	Singly list limited, doubly list flexible	Singly: 1 -> 3, Doubly: 1 <-> 3

💡 Execution stops after showing limitations of singly linked list and advantages of doubly linked list in traversal and deletion.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	Final
head	nil	points to node 1 (singly)	points to node 1 (doubly)	points to node 1 (doubly after deletion)	points to node 1
node1.next	nil	points to node 2	points to node 2	points to node 3	points to node 3
node2.prev	nil	nil (singly list)	points to node 1	nil (deleted)	nil
node3.prev	nil	nil (singly list)	points to node 2	points to node 1	points to node 1

Key Moments - 3 Insights

Why can't we move backward in a singly linked list?

Because singly linked list nodes only have 'next' pointers, no 'prev' pointers to go backward, as shown in execution_table step 2.

How does having 'prev' pointers in doubly linked list help deletion?

It allows direct access to the previous node to update pointers without traversing from head, as shown in execution_table step 6.

Does doubly linked list use more memory?

Yes, because each node stores an extra 'prev' pointer, but it gives more flexibility in traversal and deletion.

Visual Quiz - 3 Questions

Look at the execution table at step 2, why is backward traversal not possible?

A Because nodes have no 'prev' pointers

B Because head is null

C Because next pointers are broken

D Because list is empty

💡 Hint

See execution_table row 2 under 'Pointer Changes' and 'Visual State'

At which step does the doubly linked list allow backward traversal?

A Step 1

B Step 3

C Step 4

D Step 5

💡 Hint

Check execution_table row 4 'Operation' and 'Visual State'

If we remove 'prev' pointers from doubly linked list, what changes in deletion?

A Deletion becomes easier

B Deletion requires traversal from head

C Deletion is impossible

D Deletion happens automatically

💡 Hint

Refer to execution_table rows 5 and 6 comparing deletion in singly and doubly lists

Concept Snapshot

Singly Linked List nodes have only 'next' pointers.
Doubly Linked List nodes have 'next' and 'prev' pointers.
Singly lists allow forward traversal only.
Doubly lists allow forward and backward traversal.
Doubly lists make deletion easier by direct access to previous nodes.
Doubly lists use more memory but offer more flexibility.

Full Transcript

This visual execution compares singly and doubly linked lists. Singly linked lists have nodes with only 'next' pointers, so you can only move forward. This makes backward traversal and some deletions hard because you must start from the head each time. Doubly linked lists add a 'prev' pointer to each node, allowing easy backward movement and simpler deletion by updating pointers directly. The trade-off is more memory use per node. The execution table shows creating lists, trying backward traversal, and deleting nodes in both types, highlighting the advantages of doubly linked lists.

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