Traversal Forward and Backward in DSA Go - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at head node

↓

Visit current node

→Move to next node

↓

Repeat until current is nil

↓

Start at tail node

↓

Visit current node

→Move to previous node

↓

Repeat until current is nil

Traverse the list from head to tail visiting nodes forward, then from tail to head visiting nodes backward.

Execution Sample

DSA Go

package main

import "fmt"

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

// Traverse forward
func traverseForward(head *Node) {
  current := head
  for current != nil {
    fmt.Println(current.value)
    current = current.next
  }
}

// Traverse backward
func traverseBackward(tail *Node) {
  current := tail
  for current != nil {
    fmt.Println(current.value)
    current = current.prev
  }
}

func main() {
  // Example usage
  node1 := &Node{value: 1}
  node2 := &Node{value: 2}
  node3 := &Node{value: 3}
  node4 := &Node{value: 4}
  node5 := &Node{value: 5}

  // Linking nodes
  node1.next = node2
  node2.prev = node1
  node2.next = node3
  node3.prev = node2
  node3.next = node4
  node4.prev = node3
  node4.next = node5
  node5.prev = node4

  fmt.Println("Forward traversal:")
  traverseForward(node1)

  fmt.Println("Backward traversal:")
  traverseBackward(node5)
}

Traverse a doubly linked list forward from head and backward from tail printing node values.

Execution Table

Step	Operation	Current Node Value	Pointer Changes	Visual State
1	Start forward traversal at head	1	current = head (Node 1)	1 <-> 2 <-> 3 <-> 4 <-> 5
2	Visit current node	1	Print 1	1 <-> 2 <-> 3 <-> 4 <-> 5
3	Move to next node	2	current = current.next (Node 2)	1 <-> 2 <-> 3 <-> 4 <-> 5
4	Visit current node	2	Print 2	1 <-> 2 <-> 3 <-> 4 <-> 5
5	Move to next node	3	current = current.next (Node 3)	1 <-> 2 <-> 3 <-> 4 <-> 5
6	Visit current node	3	Print 3	1 <-> 2 <-> 3 <-> 4 <-> 5
7	Move to next node	4	current = current.next (Node 4)	1 <-> 2 <-> 3 <-> 4 <-> 5
8	Visit current node	4	Print 4	1 <-> 2 <-> 3 <-> 4 <-> 5
9	Move to next node	5	current = current.next (Node 5)	1 <-> 2 <-> 3 <-> 4 <-> 5
10	Visit current node	5	Print 5	1 <-> 2 <-> 3 <-> 4 <-> 5
11	Move to next node	nil	current = current.next (nil)	1 <-> 2 <-> 3 <-> 4 <-> 5
12	Forward traversal ends	nil	current is nil, stop	1 <-> 2 <-> 3 <-> 4 <-> 5
13	Start backward traversal at tail	5	current = tail (Node 5)	1 <-> 2 <-> 3 <-> 4 <-> 5
14	Visit current node	5	Print 5	1 <-> 2 <-> 3 <-> 4 <-> 5
15	Move to previous node	4	current = current.prev (Node 4)	1 <-> 2 <-> 3 <-> 4 <-> 5
16	Visit current node	4	Print 4	1 <-> 2 <-> 3 <-> 4 <-> 5
17	Move to previous node	3	current = current.prev (Node 3)	1 <-> 2 <-> 3 <-> 4 <-> 5
18	Visit current node	3	Print 3	1 <-> 2 <-> 3 <-> 4 <-> 5
19	Move to previous node	2	current = current.prev (Node 2)	1 <-> 2 <-> 3 <-> 4 <-> 5
20	Visit current node	2	Print 2	1 <-> 2 <-> 3 <-> 4 <-> 5
21	Move to previous node	1	current = current.prev (Node 1)	1 <-> 2 <-> 3 <-> 4 <-> 5
22	Visit current node	1	Print 1	1 <-> 2 <-> 3 <-> 4 <-> 5
23	Move to previous node	nil	current = current.prev (nil)	1 <-> 2 <-> 3 <-> 4 <-> 5
24	Backward traversal ends	nil	current is nil, stop	1 <-> 2 <-> 3 <-> 4 <-> 5

💡 Traversal stops when current pointer becomes nil (no more nodes to visit).

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	After Step 15	After Step 17	After Step 19	After Step 21	After Step 23
current (forward)	Node 1	Node 2	Node 3	Node 4	Node 5	nil	-	-	-	-	-	-
current (backward)	-	-	-	-	-	-	Node 5	Node 4	Node 3	Node 2	Node 1	nil

Key Moments - 3 Insights

Why does the forward traversal stop when current becomes nil?

Because the execution_table rows 11 and 12 show current moves to nil after the last node, indicating no more nodes to visit.

Why do we start backward traversal at the tail node, not the head?

Because backward traversal uses the prev pointer, so starting at tail (row 13) allows moving backward through the list as shown in rows 14-24.

What happens if the list is empty (head and tail are nil)?

Traversal loops never start because current is nil from the start, so no nodes are visited and traversal ends immediately.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current after step 7 during forward traversal?

A Node with value 4

B Node with value 3

C Node with value 5

D nil

💡 Hint

Check the 'Pointer Changes' and 'Current Node Value' columns at step 7 in execution_table.

At which step does the backward traversal first visit the node with value 3?

A Step 16

B Step 18

C Step 20

D Step 22

💡 Hint

Look at the 'Visit current node' operations in backward traversal in execution_table rows 14-24.

If the list had only one node, how would the forward traversal execution_table change?

A Traversal would print the single node and then stop at next nil immediately.

B Traversal would not start because head is nil.

C Traversal would loop infinitely.

D Traversal would skip the single node and stop.

💡 Hint

Refer to the exit condition in execution_table and key_moments about traversal stopping when current is nil.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Forward: Start at head, move next until nil
- Backward: Start at tail, move prev until nil
- Visit nodes by printing or processing value
- Stop when current pointer is nil
- Requires doubly linked list with next and prev pointers

Full Transcript

This visualization shows how to traverse a doubly linked list forward from the head node to the tail node, visiting each node by moving through the next pointers. Then it shows backward traversal starting at the tail node moving to the head by following prev pointers. The execution table tracks each step, the current node visited, pointer changes, and the visual state of the list. The variable tracker shows how the current pointer changes during traversal. Key moments clarify why traversal stops when current is nil, why backward traversal starts at tail, and what happens if the list is empty. The visual quiz tests understanding of pointer positions and traversal steps. The concept snapshot summarizes the traversal rules and pointers needed.

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