Traversal Forward and Backward in DSA Java - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at head node

↓

Visit current node

↓

Move to next node

↓

Is next node null?

No→Repeat visit

Yes↓

Reached tail node

↓

Visit current node

↓

Move to previous node

↓

Is previous node null?

No→Repeat visit

Yes↓

Traversal complete

Start from the head, move forward visiting each node until tail, then move backward visiting each node until head.

Execution Sample

DSA Java

Node current = head;
while (current != null) {
  System.out.print(current.data + " ");
  current = current.next;
}
current = tail;
while (current != null) {
  System.out.print(current.data + " ");
  current = current.prev;
}

Traverse the doubly linked list forward from head to tail, then backward from tail to head, printing each node's data.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node 1	current = head	1 <-> 2 <-> 3 <-> 4 <-> null
2	Visit current node	Node 1	print 1	1 <-> 2 <-> 3 <-> 4 <-> null
3	Move to next node	Node 2	current = current.next	1 <-> 2 <-> 3 <-> 4 <-> null
4	Visit current node	Node 2	print 2	1 <-> 2 <-> 3 <-> 4 <-> null
5	Move to next node	Node 3	current = current.next	1 <-> 2 <-> 3 <-> 4 <-> null
6	Visit current node	Node 3	print 3	1 <-> 2 <-> 3 <-> 4 <-> null
7	Move to next node	Node 4	current = current.next	1 <-> 2 <-> 3 <-> 4 <-> null
8	Visit current node	Node 4	print 4	1 <-> 2 <-> 3 <-> 4 <-> null
9	Move to next node	null	current = current.next	1 <-> 2 <-> 3 <-> 4 <-> null
10	Reached tail, start backward traversal	Node 4	current = tail	1 <-> 2 <-> 3 <-> 4 <-> null
11	Visit current node	Node 4	print 4	1 <-> 2 <-> 3 <-> 4 <-> null
12	Move to previous node	Node 3	current = current.prev	1 <-> 2 <-> 3 <-> 4 <-> null
13	Visit current node	Node 3	print 3	1 <-> 2 <-> 3 <-> 4 <-> null
14	Move to previous node	Node 2	current = current.prev	1 <-> 2 <-> 3 <-> 4 <-> null
15	Visit current node	Node 2	print 2	1 <-> 2 <-> 3 <-> 4 <-> null
16	Move to previous node	Node 1	current = current.prev	1 <-> 2 <-> 3 <-> 4 <-> null
17	Visit current node	Node 1	print 1	1 <-> 2 <-> 3 <-> 4 <-> null
18	Move to previous node	null	current = current.prev	1 <-> 2 <-> 3 <-> 4 <-> null
19	Traversal complete	null	current == null	1 <-> 2 <-> 3 <-> 4 <-> null

💡 Traversal stops when current becomes null moving forward and backward.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 12	After Step 14	After Step 16	After Step 18	Final
current	Node 1	Node 2	Node 3	Node 4	null	Node 3	Node 2	Node 1	null	null

Key Moments - 3 Insights

Why does the backward traversal start at the tail node instead of continuing from null?

Because after forward traversal current becomes null (step 9), we reset current to tail (step 10) to start backward traversal, as shown in execution_table rows 9 and 10.

Why do we check current != null before visiting nodes?

To avoid errors from accessing a null node. The traversal stops when current is null (steps 9 and 18), ensuring we only visit valid nodes.

Why does the visual state not change during traversal?

Traversal only moves the current pointer and prints data; it does not modify the list structure, so the visual state remains the same throughout.

Visual Quiz - 3 Questions

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

A Node 3

B Node 2

C Node 4

D null

💡 Hint

Check the 'current' column in execution_table row with Step 5.

At which step does the forward traversal end and backward traversal begin?

A Step 9

B Step 10

C Step 18

D Step 19

💡 Hint

Look for the step where current is reset to tail in execution_table.

If the list had only one node, how many times would the forward traversal print the node's data?

A Once

B Twice

C Zero

D Three times

💡 Hint

Consider the variable_tracker and execution_table for a single-node list scenario.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Start at head, move forward using next pointers.
- Visit each node's data until current is null.
- Then start at tail, move backward using prev pointers.
- Visit each node's data until current is null again.
- List structure remains unchanged during traversal.

Full Transcript

This visualization shows how to traverse a doubly linked list forward from head to tail, then backward from tail to head. We start with a pointer at the head node and move forward by following the next pointers, printing each node's data. When we reach the end (current becomes null), we reset the pointer to the tail node and move backward by following the prev pointers, again printing each node's data. The list's structure does not change during traversal, only the current pointer moves. The traversal ends when current becomes null in both directions.

Practice

1. What does forward traversal mean in the context of a linked list?

easy

A. Skipping every other node while visiting

B. Visiting nodes from the tail to the head in reverse order

C. Visiting nodes from the head to the tail in order

D. Visiting nodes randomly without order

Solution

1. Step 1: Understand linked list structure

   A linked list has nodes connected from head to tail in one direction.

2. Step 2: Define forward traversal

   Forward traversal means visiting nodes starting at the head and moving to the tail in order.

3. Final Answer:

   Visiting nodes from the head to the tail in order -> Option C

4. Quick Check:

   Forward traversal = head to tail [OK]

Hint: Forward means start at head and go next nodes [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal is random
• Assuming skipping nodes is traversal

2. Which Java code snippet correctly traverses a singly linked list forward?

easy

A. for(Node curr = tail; curr != null; curr = curr.prev) { System.out.print(curr.data + " "); }

B. for(Node curr = head; curr != null; curr = curr.next) { System.out.print(curr.data + " "); }

C. while(head != null) { System.out.print(head.data + " "); head = head.prev; }

D. for(Node curr = head; curr != null; curr = curr.prev) { System.out.print(curr.data + " "); }

Solution

1. Step 1: Identify forward traversal in singly linked list

   Forward traversal uses the next pointer starting from head.

2. Step 2: Check code correctness

   for(Node curr = head; curr != null; curr = curr.next) { System.out.print(curr.data + " "); } uses curr = head; curr != null; curr = curr.next which is correct for forward traversal.

3. Final Answer:

   for(Node curr = head; curr != null; curr = curr.next) { System.out.print(curr.data + " "); } -> Option B

4. Quick Check:

   Use next pointer from head for forward traversal [OK]

Hint: Use curr = curr.next starting at head for forward traversal [OK]

Common Mistakes:

• Using prev pointer in singly linked list
• Starting from tail in singly linked list
• Using wrong loop conditions

3. What is the output of this Java code for a doubly linked list with nodes 1 <-> 2 <-> 3 when traversed backward from tail?

Node tail = thirdNode; // node with data 3
Node curr = tail;
while(curr != null) {
    System.out.print(curr.data + " ");
    curr = curr.prev;
}

medium

A. 3 2 1

B. 1 2 3

C. 3 1 2

D. 2 3 1

Solution

1. Step 1: Understand doubly linked list backward traversal

   Backward traversal starts at tail and moves using prev pointer to head.

2. Step 2: Trace the loop output

   Starting at node 3, print 3, move to 2, print 2, move to 1, print 1, then stop.

3. Final Answer:

   3 2 1 -> Option A

4. Quick Check:

   Backward traversal prints 3 2 1 [OK]

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

Common Mistakes:

• Confusing forward and backward traversal
• Printing nodes in wrong order
• Using next pointer instead of prev

4. Identify the error in this code snippet that tries to traverse a doubly linked list backward:

Node curr = head;
while(curr != null) {
    System.out.print(curr.data + " ");
    curr = curr.prev;
}

medium

A. Loop condition should be curr.next != null

B. Using next pointer instead of prev pointer

C. Missing initialization of curr

D. Starting traversal from head but using prev pointer causes null pointer error

Solution

1. Step 1: Analyze traversal start and direction

   Traversal starts at head but moves using prev pointer which is null at head.

2. Step 2: Identify error cause

   Using prev from head causes immediate null pointer or no traversal backward possible.

3. Final Answer:

   Starting traversal from head but using prev pointer causes null pointer error -> Option D

4. Quick Check:

   Backward traversal must start at tail, not head [OK]

Hint: Backward traversal must start at tail node [OK]

Common Mistakes:

• Starting backward traversal at head
• Confusing prev and next pointers
• Incorrect loop conditions

5. Given a doubly linked list, how can you print its elements forward and then backward without using extra space? Choose the best approach.

hard

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

B. Traverse forward twice from head to tail printing nodes both times

C. Traverse backward twice from tail to head printing nodes both times

D. Store all nodes in an array then print forward and backward from array

Solution

1. Step 1: Understand traversal without extra space

   Using the doubly linked list pointers allows forward and backward traversal without extra storage.

2. Step 2: Apply forward then backward traversal

   First traverse from head to tail printing nodes, then from tail to head printing nodes using prev pointers.

3. Final Answer:

   Traverse forward from head to tail printing nodes, then traverse backward from tail to head printing nodes -> Option A

4. Quick Check:

   Use head and tail pointers for forward and backward traversal [OK]

Hint: Use head for forward and tail for backward traversal [OK]

Common Mistakes:

• Using extra space unnecessarily
• Traversing only forward twice
• Confusing traversal directions