Traversal Forward and Backward in DSA Go - Build from Scratch

Traversal Forward and Backward in a Doubly Linked List

📖 Scenario: You are building a simple contact list app. The contacts are stored in a doubly linked list so you can move forward and backward through the list easily.

🎯 Goal: Create a doubly linked list with three contacts. Then, traverse the list forward to print all contacts, and traverse backward to print all contacts in reverse order.

📋 What You'll Learn

Create a doubly linked list node struct with name, prev, and next fields

Create three nodes with names exactly "Alice", "Bob", and "Charlie"

Link the nodes to form a doubly linked list

Traverse the list forward starting from the head node and collect the names

Traverse the list backward starting from the tail node and collect the names

Print the forward traversal result as a string with names separated by " -> "

Print the backward traversal result as a string with names separated by " -> "

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in applications like music players to move forward and backward through songs, or in browsers to navigate forward and backward through pages.

💼 Career

Understanding doubly linked lists helps in jobs involving system programming, game development, and any software that requires efficient two-way navigation through data.

1

Create the doubly linked list nodes

Create a struct called Node with fields name (string), prev (*Node), and next (*Node). Then create three variables called node1, node2, and node3 of type Node with names "Alice", "Bob", and "Charlie" respectively.

DSA Go

// Define Node struct and create node1, node2, node3 with names
// Your code here

Hint

Define the struct first, then create three variables of that struct type with the exact names.

2

Link the nodes to form a doubly linked list

Link the nodes so that node1.next points to &node2, node2.prev points to &node1, node2.next points to &node3, and node3.prev points to &node2. Also create two variables called head and tail that point to &node1 and &node3 respectively.

DSA Go

package main

type Node struct {
    name string
    prev *Node
    next *Node
}

func main() {
    node1 := Node{name: "Alice"}
    node2 := Node{name: "Bob"}
    node3 := Node{name: "Charlie"}
    // Link nodes and create head and tail
    // Your code here
}

Hint

Set the next and prev pointers to link the nodes forward and backward. Then assign head and tail to the first and last nodes.

3

Traverse forward and backward to collect names

Create two slices of strings called forwardNames and backwardNames. Traverse the list forward starting from head and append each node's name to forwardNames. Then traverse backward starting from tail and append each node's name to backwardNames.

DSA Go

package main

type Node struct {
    name string
    prev *Node
    next *Node
}

func main() {
    node1 := Node{name: "Alice"}
    node2 := Node{name: "Bob"}
    node3 := Node{name: "Charlie"}

    node1.next = &node2
    node2.prev = &node1
    node2.next = &node3
    node3.prev = &node2

    head := &node1
    tail := &node3

    // Traverse forward and backward to collect names
    // Your code here
}

Hint

Use a for loop to move forward using next pointers and backward using prev pointers, appending names to slices.

4

Print the forward and backward traversal results

Use fmt.Println to print the forward traversal names joined by " -> " as Forward: Alice -> Bob -> Charlie. Then print the backward traversal names joined by " -> " as Backward: Charlie -> Bob -> Alice. Import fmt and strings packages.

DSA Go

package main

import (
    "fmt"
    "strings"
)

type Node struct {
    name string
    prev *Node
    next *Node
}

func main() {
    node1 := Node{name: "Alice"}
    node2 := Node{name: "Bob"}
    node3 := Node{name: "Charlie"}

    node1.next = &node2
    node2.prev = &node1
    node2.next = &node3
    node3.prev = &node2

    head := &node1
    tail := &node3

    forwardNames := []string{}
    for current := head; current != nil; current = current.next {
        forwardNames = append(forwardNames, current.name)
    }

    backwardNames := []string{}
    for current := tail; current != nil; current = current.prev {
        backwardNames = append(backwardNames, current.name)
    }

    // Print forward and backward traversal results
    // Your code here
}

Hint

Use strings.Join(slice, " -> ") to join names and fmt.Println to print the results.

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