Traversal Forward and Backward in DSA C# - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at Head Node

↓

Visit Current Node

→Move to Next Node?

↓

Repeat Until Last Node

↓

Start at Tail Node

↓

Traversal Forward Done

↓

Visit Current Node

→Move to Previous Node?

↓

Repeat Until Head Node

↓

Traversal Backward Done

Start from the head node and move forward visiting each node until the last. Then start from the tail node and move backward visiting each node until the head.

Execution Sample

DSA C#

Node current = head;
while (current != null) {
  Console.Write(current.Value + " -> ");
  current = current.Next;
}

current = tail;
while (current != null) {
  Console.Write(current.Value + " -> ");
  current = current.Prev;
}

Traverse a doubly linked list forward from head to tail, then backward from tail to head, printing node values.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start forward traversal	Node 1 (Head)	current = head	1 <-> 2 <-> 3 <-> 4 <-> 5
2	Visit node	Node 1	Print 1	1 <-> 2 <-> 3 <-> 4 <-> 5
3	Move to next	Node 2	current = current.Next	1 <-> 2 <-> 3 <-> 4 <-> 5
4	Visit node	Node 2	Print 2	1 <-> 2 <-> 3 <-> 4 <-> 5
5	Move to next	Node 3	current = current.Next	1 <-> 2 <-> 3 <-> 4 <-> 5
6	Visit node	Node 3	Print 3	1 <-> 2 <-> 3 <-> 4 <-> 5
7	Move to next	Node 4	current = current.Next	1 <-> 2 <-> 3 <-> 4 <-> 5
8	Visit node	Node 4	Print 4	1 <-> 2 <-> 3 <-> 4 <-> 5
9	Move to next	Node 5 (Tail)	current = current.Next	1 <-> 2 <-> 3 <-> 4 <-> 5
10	Visit node	Node 5	Print 5	1 <-> 2 <-> 3 <-> 4 <-> 5
11	Move to next	null	current = current.Next	1 <-> 2 <-> 3 <-> 4 <-> 5
12	Forward traversal done	null	current == null	1 <-> 2 <-> 3 <-> 4 <-> 5
13	Start backward traversal	Node 5 (Tail)	current = tail	1 <-> 2 <-> 3 <-> 4 <-> 5
14	Visit node	Node 5	Print 5	1 <-> 2 <-> 3 <-> 4 <-> 5
15	Move to previous	Node 4	current = current.Prev	1 <-> 2 <-> 3 <-> 4 <-> 5
16	Visit node	Node 4	Print 4	1 <-> 2 <-> 3 <-> 4 <-> 5
17	Move to previous	Node 3	current = current.Prev	1 <-> 2 <-> 3 <-> 4 <-> 5
18	Visit node	Node 3	Print 3	1 <-> 2 <-> 3 <-> 4 <-> 5
19	Move to previous	Node 2	current = current.Prev	1 <-> 2 <-> 3 <-> 4 <-> 5
20	Visit node	Node 2	Print 2	1 <-> 2 <-> 3 <-> 4 <-> 5
21	Move to previous	Node 1 (Head)	current = current.Prev	1 <-> 2 <-> 3 <-> 4 <-> 5
22	Visit node	Node 1	Print 1	1 <-> 2 <-> 3 <-> 4 <-> 5
23	Move to previous	null	current = current.Prev	1 <-> 2 <-> 3 <-> 4 <-> 5
24	Backward traversal done	null	current == null	1 <-> 2 <-> 3 <-> 4 <-> 5

💡 Traversal stops when current becomes null after last node in forward and before first node in backward traversal.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 15	After Step 17	After Step 19	After Step 21	After Step 23	Final
current	Node 1 (Head)	Node 2	Node 3	Node 4	Node 5 (Tail)	null	Node 4	Node 3	Node 2	Node 1 (Head)	null	null

Key Moments - 3 Insights

Why does the forward traversal stop when current becomes null?

Because in the execution_table at step 11, current moves from Node 5 to null, indicating no more nodes ahead to visit.

Why do we start backward traversal from the tail node?

As shown in step 13, backward traversal begins at tail because we want to visit nodes in reverse order using the Prev pointer.

What happens if the list is empty (head is null)?

Traversal loops never start because current is null from the start, so no nodes are visited, as implied by the exit condition in step 12.

Visual Quiz - 3 Questions

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

A Node 4

B Node 3

C Node 5

D null

💡 Hint

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

At which step does the forward traversal end?

A Step 11

B Step 12

C Step 24

D Step 10

💡 Hint

Look for the row where 'Forward traversal done' is noted in the 'Operation' column.

If the list had only one node, how many times would the forward traversal print a value?

A 0 times

B 1 time

C 2 times

D Depends on the node value

💡 Hint

Refer to the execution_table steps 2 and 10 where nodes are visited and printed.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Start at head, visit nodes moving via Next pointer until null
- Then start at tail, visit nodes moving via Prev pointer until null
- Print or process each node during visits
- Stops when current pointer becomes null
- Useful to access list in both directions easily

Full Transcript

This concept shows how to traverse a doubly linked list forward from the head node to the tail node by following the Next pointers, visiting each node and printing its value. After reaching the tail, traversal continues backward from the tail to the head by following the Prev pointers, again visiting and printing each node. The traversal stops when the current pointer becomes null, indicating no more nodes in that direction. The execution table tracks each step, showing the current node, pointer changes, and the visual state of the list. The variable tracker shows how the current pointer moves through the list during forward and backward traversal. Key moments clarify why traversal stops at null and why backward traversal starts at the tail. The visual quiz tests understanding of pointer positions and traversal end conditions. This method allows easy access to nodes in both directions in a doubly linked list.

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. Visiting nodes randomly without order

D. Visiting nodes only from the end to the start

Solution

1. Step 1: Understand traversal directions

   Traversal forward means visiting nodes from the first node to the last node. Traversal backward means visiting nodes from the last node back to the first node.

2. Step 2: Apply to doubly linked list

   A doubly linked list allows moving in both directions because each node has links to the next and previous nodes.

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:

   Forward and backward traversal = visiting nodes both ways [OK]

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

Common Mistakes:

• Confusing traversal with random access
• Thinking traversal is only forward
• Ignoring backward links in doubly linked list

2. Which of the following is the correct syntax to traverse a doubly linked list forward in C#?

easy

A. for(Node current = tail; current != null; current = current.Next) { /* process current */ }

B. for(Node current = head; current != null; current = current.Next) { /* process current */ }

C. for(Node current = head; current != null; current = current.Prev) { /* process current */ }

D. for(Node current = tail; current != null; current = current.Prev) { /* process current */ }

Solution

1. Step 1: Identify forward traversal

   Forward traversal starts at the head and moves to the next node repeatedly until null.

2. Step 2: Check syntax correctness

   for(Node current = head; current != null; current = current.Next) { /* process current */ } correctly starts at head and moves using current = current.Next. Other options either start at tail or move backward.

3. Final Answer:

   for(Node current = head; current != null; current = current.Next) { /* process current */ } -> Option B

4. Quick Check:

   Forward traversal uses Next pointer from head [OK]

Hint: Forward means start at head and use Next [OK]

Common Mistakes:

• Starting at tail for forward traversal
• Using Prev pointer for forward traversal
• Confusing Next and Prev pointers

3. Given the doubly linked list with nodes containing values 1, 2, 3, 4, what is the output of this forward traversal code?

Node current = head;
while(current != null) {
    Console.Write(current.Value + " -> ");
    current = current.Next;
}
Console.WriteLine("null");

medium

A. null

B. 4 -> 3 -> 2 -> 1 -> null

C. 1 -> 2 -> 3 -> 4 -> null

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Understand the list structure

   The list nodes are 1 linked to 2, then 3, then 4, in order.

2. Step 2: Trace the forward traversal

   Starting at head (1), print 1, move to 2, print 2, move to 3, print 3, move to 4, print 4, then current becomes null and loop ends.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> null -> Option C

4. Quick Check:

   Forward traversal prints nodes in order [OK]

Hint: Follow Next pointers from head to null [OK]

Common Mistakes:

• Printing backward order instead of forward
• Missing last node in output
• Printing null before nodes

4. Identify the error in this backward traversal code of a doubly linked list:

Node current = head;
while(current != null) {
    Console.Write(current.Value + " <- ");
    current = current.Prev;
}
Console.WriteLine("null");

medium

A. Missing null check in loop

B. Using Prev pointer instead of Next

C. Incorrect print format

D. Starting traversal from head instead of tail

Solution

1. Step 1: Understand backward traversal

   Backward traversal should start from the tail node, not the head.

2. Step 2: Analyze given code

   The code starts at head and tries to move backward using Prev, but head.Prev is null, so loop ends immediately.

3. Final Answer:

   Starting traversal from head instead of tail -> Option D

4. Quick Check:

   Backward traversal must start at tail [OK]

Hint: Backward means start at tail, not head [OK]

Common Mistakes:

• Starting backward traversal at head
• Confusing Prev and Next pointers
• Ignoring list ends (null pointers)

5. You have a doubly linked list with nodes: 10 <-> 20 <-> 30 <-> 40. Write a method to print the list forward and then backward without using extra data structures. What will be the output?

hard

A. 10 -> 20 -> 30 -> 40 -> null
40 -> 30 -> 20 -> 10 -> null

B. 40 -> 30 -> 20 -> 10 -> null
10 -> 20 -> 30 -> 40 -> null

C. 10 -> 20 -> 30 -> 40 -> null
null

D. null
40 -> 30 -> 20 -> 10 -> null

Solution

1. Step 1: Traverse forward from head to tail

   Start at head (10), print each node's value moving via Next until null: 10 -> 20 -> 30 -> 40 -> null.

2. Step 2: Traverse backward from tail to head

   After reaching tail (40), move backward using Prev pointer, printing: 40 -> 30 -> 20 -> 10 -> null.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> null 40 -> 30 -> 20 -> 10 -> null -> Option A

4. Quick Check:

   Forward then backward traversal prints nodes in both directions [OK]

Hint: Print forward using Next, backward using Prev [OK]

Common Mistakes:

• Trying to traverse backward from head
• Printing null before nodes
• Using extra data structures unnecessarily