Why Doubly Linked List Over Singly Linked List in DSA Go - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why choose a doubly linked list over a singly linked list?

Which of the following is the main advantage of using a doubly linked list instead of a singly linked list?

A It simplifies insertion only at the end of the list.

B It uses less memory per node compared to singly linked list.

C It eliminates the need for a head pointer.

D It allows traversal in both forward and backward directions easily.

💡 Hint

Think about how you can move through the list in both directions.

Doubly linked lists have two pointers per node, allowing easy movement forward and backward. Singly linked lists only allow forward traversal.

❓ Predict Output

intermediate

Output of traversal in doubly linked list

What will be the printed output of the following Go code that traverses a doubly linked list backward?

DSA Go

package main
import "fmt"

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

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

    current := n3
    for current != nil {
        fmt.Print(current.data)
        if current.prev != nil {
            fmt.Print(" <-> ")
        }
        current = current.prev
    }
}

A 3 <-> 2 <-> 1

B 1 <-> 2 <-> 3

C 3 -> 2 -> 1

D 1 -> 2 -> 3

💡 Hint

The code starts from the last node and moves backward using the prev pointer.

The traversal starts at node with data 3 and moves backward through prev pointers, printing 3, 2, then 1 with arrows between.

🔧 Debug

advanced

Identify the error in doubly linked list insertion

What error will the following Go code produce when inserting a new node after the head in a doubly linked list?

DSA Go

package main
import "fmt"

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

func main() {
    head := &Node{data: 1}
    second := &Node{data: 2}
    head.next = second
    second.prev = head

    newNode := &Node{data: 3}
    newNode.next = head.next
    head.next = newNode
    newNode.prev = head

    fmt.Println(head.next.next.data)
}

A Prints 3

B Prints 2

C runtime error: invalid memory address or nil pointer dereference

D Compilation error

💡 Hint

Check if all pointers are updated correctly after insertion.

The code forgets to update the prev pointer of the original second node to point to the new node, causing a broken link and runtime error when accessing head.next.next.data.

❓ Predict Output

advanced

Result of removing a node from doubly linked list

What will be the printed output after removing the middle node from this doubly linked list?

DSA Go

package main
import "fmt"

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

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

    // Remove n2
    n1.next = n3
    n3.prev = n1

    current := n1
    for current != nil {
        fmt.Print(current.data)
        if current.next != nil {
            fmt.Print(" -> ")
        }
        current = current.next
    }
}

A 1 -> 2 -> 3

B 1 -> 3

C 2 -> 3

D 1

💡 Hint

After removal, the list should skip the removed node.

The middle node with data 2 is removed by linking node 1 directly to node 3, so the output prints 1 -> 3.

🧠 Conceptual

expert

Memory trade-offs of doubly linked lists

Which statement best describes the memory trade-off when using a doubly linked list compared to a singly linked list?

A Doubly linked lists use more memory per node but allow efficient backward traversal and deletion.

B Doubly linked lists use less memory per node and are faster for all operations.

C Doubly linked lists use the same memory but are slower due to extra pointers.

D Doubly linked lists use more memory but do not improve traversal capabilities.

💡 Hint

Consider the number of pointers stored in each node and the operations enabled.

Doubly linked lists store two pointers per node, increasing memory use, but this enables efficient backward traversal and easier node deletion compared to singly 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