Traversal Forward and Backward in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Forward and Backward Traversal in Doubly Linked List

What is the printed output after running this Go code that traverses a doubly linked list forward and then backward?

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}
    third := &Node{data: 3}
    head.next = second
    second.prev = head
    second.next = third
    third.prev = second

    // Forward traversal
    current := head
    for current != nil {
        fmt.Print(current.data, " ")
        if current.next == nil {
            break
        }
        current = current.next
    }
    fmt.Print("| ")

    // Backward traversal
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.prev
    }
}

A 1 2 3 | 3 2 1

B 1 2 3 | 1 2 3

C 3 2 1 | 1 2 3

D 3 2 1 | 3 2 1

💡 Hint

Think about how the pointers move forward and backward in a doubly linked list.

The forward loop prints nodes from head to tail: 1 2 3. Then the backward loop prints from tail back to head: 3 2 1.

🧠 Conceptual

intermediate

Understanding Traversal Direction in Doubly Linked Lists

In a doubly linked list, which pointer do you follow to traverse the list backward from the tail node?

A The tail pointer

B The next pointer

C The head pointer

D The prev pointer

💡 Hint

Backward means going to the previous node.

The prev pointer points to the previous node, so following prev pointers from tail moves backward.

🔧 Debug

advanced

Identify the Bug in Backward Traversal Code

What error will this Go code produce when trying to traverse backward 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

    current := head
    // Attempt backward traversal starting from head
    for current != nil {
        fmt.Print(current.data, " ")
        current = current.prev
    }
}

A Runtime panic due to nil pointer dereference

B Prints 1 2 and then stops

C Prints 1 and then stops

D Infinite loop

💡 Hint

Think about what prev pointer of head points to.

Head's prev pointer is nil, so the loop prints 1 and stops immediately.

❓ Predict Output

advanced

Output of Mixed Forward and Backward Traversal

What is the output of this Go code that traverses forward two nodes and then backward one node in a doubly linked list?

DSA Go

package main
import "fmt"
type Node struct {
    data int
    prev *Node
    next *Node
}
func main() {
    n1 := &Node{data: 10}
    n2 := &Node{data: 20}
    n3 := &Node{data: 30}
    n1.next = n2
    n2.prev = n1
    n2.next = n3
    n3.prev = n2

    current := n1
    // Move forward two nodes
    for i := 0; i < 2; i++ {
        current = current.next
        fmt.Print(current.data, " ")
    }
    // Move backward one node
    current = current.prev
    fmt.Print("| ", current.data)
}

A 20 30 | 20

B 20 30 | 30

C 10 20 | 10

D 30 20 | 20

💡 Hint

Trace the pointer moves carefully step by step.

Forward moves print 20 then 30. Then moving backward one node from 30 goes to 20.

🧠 Conceptual

expert

Why Use Doubly Linked List for Forward and Backward Traversal?

Which is the main advantage of a doubly linked list over a singly linked list when traversing forward and backward?

A It uses less memory per node

B It allows traversal in both directions efficiently

C It requires fewer pointers to manage

D It automatically sorts the data

💡 Hint

Think about how pointers connect nodes in both types of lists.

Doubly linked lists have prev and next pointers, enabling efficient forward and backward traversal.

Practice

1. What does "Traversal Forward and Backward" mean in the context of a doubly linked list?

easy

A. Visiting nodes from the start to the end and then from the end back to the start

B. Only visiting nodes from the start to the end

C. Only visiting nodes from the end to the start

D. Skipping nodes randomly during traversal

Solution

1. Step 1: Understand forward traversal

   Forward traversal means visiting nodes starting from the first node and moving to the last node.

2. Step 2: Understand backward traversal

   Backward traversal means visiting nodes starting from the last node and moving back to the first node.

3. Final Answer:

   Visiting nodes from the start to the end and then from the end back to the start -> Option A

4. Quick Check:

   Traversal forward and backward = visiting nodes both ways [OK]

Hint: Think of walking forward then turning back [OK]

Common Mistakes:

• Confusing forward traversal with backward traversal
• Thinking traversal only goes one way
• Assuming traversal skips nodes

2. Which of the following Go code snippets correctly traverses a doubly linked list forward?

easy

A. for node := head; node != nil; node = node.prev { fmt.Println(node.value) }

B. for node := head; node != nil; node = node.next { fmt.Println(node.value) }

C. for node := tail; node != nil; node = node.next { fmt.Println(node.value) }

D. for node := tail; node != nil; node = node.prev { fmt.Println(node.value) }

Solution

1. Step 1: Identify forward traversal start point

   Forward traversal starts at the head (first node).

2. Step 2: Identify correct pointer for forward traversal

   Moving forward uses the next pointer, so node = node.next is correct.

3. Final Answer:

   for node := head; node != nil; node = node.next { fmt.Println(node.value) } -> Option B

4. Quick Check:

   Forward traversal uses head and next pointer [OK]

Hint: Forward traversal starts at head and uses next [OK]

Common Mistakes:

• Starting traversal at tail for forward direction
• Using prev pointer for forward traversal
• Confusing next and prev pointers

3. What is the output of the following Go code snippet that traverses a doubly linked list backward?

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

func main() {
  n1 := &Node{value: 1}
  n2 := &Node{value: 2}
  n3 := &Node{value: 3}
  n1.next = n2
  n2.prev = n1
  n2.next = n3
  n3.prev = n2

  for node := n3; node != nil; node = node.prev {
    fmt.Print(node.value, " ")
  }
}

medium

A. 3 1 2

B. 1 2 3

C. 3 2 1

D. 2 3 1

Solution

1. Step 1: Understand backward traversal start

   The loop starts at n3 (value 3) and moves backward using prev pointer.

2. Step 2: Trace the loop values

   First prints 3, then moves to n2 (2), prints 2, then moves to n1 (1), prints 1, then stops at nil.

3. Final Answer:

   3 2 1 -> Option C

4. Quick Check:

   Backward traversal prints 3 2 1 [OK]

Hint: Backward traversal prints values from tail to head [OK]

Common Mistakes:

• Confusing order of printing
• Starting traversal at head for backward
• Using next pointer instead of prev

4. Identify the error in the following Go code that attempts to traverse a doubly linked list backward:

for node := head; node != nil; node = node.prev {
  fmt.Println(node.value)
}

medium

A. Starting traversal at head but moving backward with prev pointer

B. Using fmt.Println instead of fmt.Print

C. Missing initialization of node variable

D. Loop condition should be node == nil

Solution

1. Step 1: Check traversal start and direction

   The code starts at head (first node) but moves backward using prev pointer, which is incorrect because head.prev is nil.

2. Step 2: Identify correct traversal logic

   Backward traversal should start at tail, not head, when moving with prev pointer.

3. Final Answer:

   Starting traversal at head but moving backward with prev pointer -> Option A

4. Quick Check:

   Backward traversal must start at tail [OK]

Hint: Backward traversal starts at tail, not head [OK]

Common Mistakes:

• Starting backward traversal at head
• Confusing loop condition
• Ignoring pointer directions

5. Given a doubly linked list, how would you print all elements first forward and then backward without repeating the last element twice in Go?

hard

A. Traverse backward printing all nodes, then traverse forward starting from head to tail

B. Traverse forward printing all nodes, then traverse backward starting from tail to head

C. Traverse forward printing all nodes, then traverse backward starting from head.prev to tail

D. Traverse forward printing all nodes, then traverse backward starting from tail.prev to head

Solution

1. Step 1: Traverse forward and print all nodes

   Start from head and print each node until tail inclusive.

2. Step 2: Traverse backward starting from tail.prev to avoid duplicate tail

   Start backward traversal from tail.prev to head to avoid printing tail twice.

3. Final Answer:

   Traverse forward printing all nodes, then traverse backward starting from tail.prev to head -> Option D

4. Quick Check:

   Skip last node in backward traversal to avoid duplicate print [OK]

Hint: Skip tail in backward traversal to avoid duplicate print [OK]

Common Mistakes:

• Printing tail twice by starting backward at tail
• Starting backward traversal incorrectly
• Confusing traversal directions