Traversal Forward and Backward in DSA Go

Mental Model

Traversal means visiting each item in a list one by one, either from start to end or from end to start.

Analogy: Imagine walking through a line of people holding hands. Walking forward means starting from the first person and moving to the last. Walking backward means starting from the last person and moving to the first.

Head -> 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑
Current at head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4, traverse forward then backward

Goal: Visit all nodes from first to last, then from last back to first

Step 1: Start at head node (1) for forward traversal

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

Why: We begin traversal from the first node

Step 2: Move forward to node 2

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

Why: Visit next node in forward direction

Step 3: Move forward to node 3

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

Why: Continue forward traversal

Step 4: Move forward to node 4 (last node)

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

Why: Reached the last node in forward traversal

Step 5: Start backward traversal from last node (4)

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

Why: Begin moving backward from the last node

Step 6: Move backward to node 3

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

Why: Visit previous node in backward direction

Step 7: Move backward to node 2

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

Why: Continue backward traversal

Step 8: Move backward to node 1 (head)

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

Why: Reached the first node in backward traversal

Result:

Forward traversal order: 1 -> 2 -> 3 -> 4 -> null
Backward traversal order: 4 -> 3 -> 2 -> 1 -> null

Annotated Code

DSA Go

package main

import "fmt"

// Node represents a doubly linked list node
type Node struct {
	value int
	prev  *Node
	next  *Node
}

// DoublyLinkedList holds the head and tail of the list
type DoublyLinkedList struct {
	head *Node
	tail *Node
}

// Append adds a new node with given value at the end
func (dll *DoublyLinkedList) Append(val int) {
	newNode := &Node{value: val}
	if dll.head == nil {
		dll.head = newNode
		dll.tail = newNode
		return
	}
	dll.tail.next = newNode
	newNode.prev = dll.tail
	dll.tail = newNode
}

// TraverseForward prints the list from head to tail
func (dll *DoublyLinkedList) TraverseForward() {
	curr := dll.head
	for curr != nil {
		fmt.Printf("%d -> ", curr.value) // print current node value
		curr = curr.next // move forward to next node
	}
	fmt.Println("null")
}

// TraverseBackward prints the list from tail to head
func (dll *DoublyLinkedList) TraverseBackward() {
	curr := dll.tail
	for curr != nil {
		fmt.Printf("%d -> ", curr.value) // print current node value
		curr = curr.prev // move backward to previous node
	}
	fmt.Println("null")
}

func main() {
	dll := &DoublyLinkedList{}
	dll.Append(1)
	dll.Append(2)
	dll.Append(3)
	dll.Append(4)

	fmt.Println("Forward traversal order:")
	dll.TraverseForward()

	fmt.Println("Backward traversal order:")
	dll.TraverseBackward()
}

curr := dll.head

start traversal from head node

curr = curr.next

advance forward to next node

curr := dll.tail

start traversal from tail node

curr = curr.prev

move backward to previous node

Output

Forward traversal order:

1 -> 2 -> 3 -> 4 -> null

Backward traversal order:

4 -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once in forward and once in backward traversal

Space: O(1) because traversal uses only a few pointers, no extra space proportional to n

vs Alternative: Compared to singly linked list, backward traversal is not possible without extra memory or reversing the list, so doubly linked list traversal is more flexible

Edge Cases

empty list

traversal prints 'null' immediately without errors

DSA Go

if dll.head == nil { dll.tail = nil; return }

single node list

forward and backward traversal print the single node value once

DSA Go

dll.tail = newNode when list is empty

When to Use This Pattern

When you need to visit elements in both directions efficiently, look for doubly linked list traversal patterns because they allow forward and backward moves easily.

Common Mistakes

Mistake: Trying to move backward in a singly linked list without storing previous nodes
Fix: Use a doubly linked list or store nodes in a stack to simulate backward traversal

Summary

It visits all nodes in a doubly linked list from start to end and then from end to start.

Use it when you want to read or process data in both forward and backward directions efficiently.

The key is that each node links to both next and previous nodes, allowing easy movement both ways.

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