Traversal Forward and Backward in DSA Python - Execution Trace

Concept Flow - Traversal Forward and Backward

Start at head node

↓

Visit current node

↓

Move to next node

↓

Is current node None?

No→Repeat visit

Yes↓

Reached end, start backward traversal

↓

Visit current node

↓

Move to previous node

↓

Is current node None?

No→Repeat visit

Yes↓

Traversal complete

Traverse nodes from head to tail visiting each node forward, then traverse backward from tail to head visiting each node.

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

# Traverse forward and backward

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

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at head	Node(1)	None	1 <-> 2 <-> 3 <-> 4 <-> None
2	Visit node	Node(1)	None	1 <-> 2 <-> 3 <-> 4 <-> None
3	Move next	Node(2)	None	1 <-> 2 <-> 3 <-> 4 <-> None
4	Visit node	Node(2)	None	1 <-> 2 <-> 3 <-> 4 <-> None
5	Move next	Node(3)	None	1 <-> 2 <-> 3 <-> 4 <-> None
6	Visit node	Node(3)	None	1 <-> 2 <-> 3 <-> 4 <-> None
7	Move next	Node(4)	None	1 <-> 2 <-> 3 <-> 4 <-> None
8	Visit node	Node(4)	None	1 <-> 2 <-> 3 <-> 4 <-> None
9	Move next	None	None	1 <-> 2 <-> 3 <-> 4 <-> None
10	Start backward at tail	Node(4)	None	1 <-> 2 <-> 3 <-> 4 <-> None
11	Visit node	Node(4)	None	1 <-> 2 <-> 3 <-> 4 <-> None
12	Move prev	Node(3)	None	1 <-> 2 <-> 3 <-> 4 <-> None
13	Visit node	Node(3)	None	1 <-> 2 <-> 3 <-> 4 <-> None
14	Move prev	Node(2)	None	1 <-> 2 <-> 3 <-> 4 <-> None
15	Visit node	Node(2)	None	1 <-> 2 <-> 3 <-> 4 <-> None
16	Move prev	Node(1)	None	1 <-> 2 <-> 3 <-> 4 <-> None
17	Visit node	Node(1)	None	1 <-> 2 <-> 3 <-> 4 <-> None
18	Move prev	None	None	1 <-> 2 <-> 3 <-> 4 <-> None
19	Traversal complete	None	None	1 <-> 2 <-> 3 <-> 4 <-> None

💡 Traversal stops when current node becomes None in both forward and backward directions.

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
current	Node(1)	Node(2)	Node(3)	Node(4)	None	Node(3)	Node(2)	Node(1)	None
direction	forward	forward	forward	forward	forward	backward	backward	backward	backward

Key Moments - 3 Insights

Why do we check if current node is None to stop traversal?

Because when current becomes None, it means we have moved past the last node (forward) or before the first node (backward), so traversal ends. See steps 9 and 18 in execution_table.

Why do we need both next and prev pointers in traversal?

Next pointer lets us move forward, prev pointer lets us move backward. Without prev, backward traversal is not possible. This is shown by pointer changes in execution_table where current moves using next or prev.

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

Traversal stops immediately because current is None at start, so no nodes are visited. This is implied by exit condition in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the current node at step 7?

A Node(3)

B Node(4)

C Node(2)

D None

💡 Hint

Check the 'Current Node' column at step 7 in execution_table.

At which step does the forward traversal end?

A Step 9

B Step 18

C Step 19

D Step 8

💡 Hint

Look for when current node becomes None during forward traversal in execution_table.

If the list had only one node, how many visit operations would happen in total?

A 1

B 2

C 3

D 4

💡 Hint

Consider visiting the single node forward and backward as shown in execution_table steps.

Concept Snapshot

Traversal Forward and Backward in Doubly Linked List:
- Start at head, visit nodes moving via next pointer.
- Stop when current is None (end of list).
- Then start at tail, visit nodes moving via prev pointer.
- Stop when current is None (start of list).
- Requires next and prev pointers for bidirectional traversal.

Full Transcript

This concept shows how to traverse a doubly linked list forward from head to tail by following the next pointers, visiting each node. When the end is reached (current node is None), traversal reverses direction starting from the tail node, moving backward by following prev pointers until the start is reached (current node is None again). The execution table traces each step, showing the current node visited and the unchanged list structure. Key moments clarify why traversal stops when current is None and why both next and prev pointers are needed. The visual quiz tests understanding of node positions at specific steps and the total visits for a single-node list.

Practice

1. What does traversal forward mean when moving through a list?

easy

A. Visiting elements randomly

B. Visiting elements from the last to the first

C. Visiting elements from the first to the last

D. Skipping every other element

Solution

1. Step 1: Understand traversal direction

   Traversal forward means starting at the beginning of the list and moving step-by-step to the end.

2. Step 2: Compare options

   Only Visiting elements from the first to the last describes visiting elements from first to last, which matches forward traversal.

3. Final Answer:

   Visiting elements from the first to the last -> Option C

4. Quick Check:

   Forward traversal = first to last [OK]

Hint: Forward means start to end in order [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal means skipping elements
• Assuming traversal is random

2. Which of the following Python loops correctly traverses a list items backward?

easy

A. for i in range(len(items)): print(items[i])

B. for i in range(len(items)-1, -1, -1): print(items[i])

C. for i in items: print(i)

D. for i in range(0, len(items), 2): print(items[i])

Solution

1. Step 1: Identify backward traversal syntax

   Backward traversal uses a loop that starts from the last index and moves to the first, decreasing the index.

2. Step 2: Check each option

   for i in range(len(items)-1, -1, -1): print(items[i]) uses range(len(items)-1, -1, -1), which counts backward correctly.

3. Final Answer:

   for i in range(len(items)-1, -1, -1): print(items[i]) -> Option B

4. Quick Check:

   Backward loop uses decreasing range [OK]

Hint: Use range with step -1 for backward loops [OK]

Common Mistakes:

• Using range(len(items)) for backward traversal
• Forgetting to set step as -1
• Using direct iteration which is forward only

3. What is the output of this code?

items = [10, 20, 30]
for i in range(len(items)-1, -1, -1):
    print(items[i], end=' ')

medium

A. 30 20 10

B. 10 20 30

C. 0 1 2

D. SyntaxError

Solution

1. Step 1: Understand the loop range

   The loop runs from index 2 down to 0 (inclusive), so it visits indices 2, 1, 0 in order.

2. Step 2: Print elements in backward order

   items[2] = 30, items[1] = 20, items[0] = 10, printed with spaces.

3. Final Answer:

   30 20 10 -> Option A

4. Quick Check:

   Backward print = 30 20 10 [OK]

Hint: Backward range prints list in reverse order [OK]

Common Mistakes:

• Confusing index order and printing forward
• Misreading range parameters
• Expecting index numbers instead of list values

4. Find the error in this backward traversal code:

items = [1, 2, 3, 4]
for i in range(len(items)):
    print(items[len(items)-i])

medium

A. IndexError due to out-of-range index

B. SyntaxError because of missing colon

C. Prints elements forward instead of backward

D. No error, prints backward correctly

Solution

1. Step 1: Analyze index calculation

   Index used is len(items)-i. For i=0, index is 4, which is out of range (max index 3).

2. Step 2: Identify error type

   Accessing index 4 causes IndexError because list indices go from 0 to 3.

3. Final Answer:

   IndexError due to out-of-range index -> Option A

4. Quick Check:

   Index out of range = IndexError [OK]

Hint: Check if index goes beyond list length [OK]

Common Mistakes:

• Using len(items)-i instead of len(items)-1-i
• Ignoring zero-based indexing
• Assuming no error if code runs partially

5. Given a doubly linked list with nodes head and tail, which approach correctly prints all elements forward then backward?

hard

A. Traverse from tail to head, then from head to tail

B. Traverse only from head to tail twice

C. Traverse randomly from any node

D. Traverse from head to tail printing, then from tail to head printing

Solution

1. Step 1: Understand doubly linked list traversal

   Doubly linked lists allow moving forward from head to tail and backward from tail to head using next and prev pointers.

2. Step 2: Identify correct traversal order

   To print forward then backward, first traverse from head to tail, then from tail to head.

3. Final Answer:

   Traverse from head to tail printing, then from tail to head printing -> Option D

4. Quick Check:

   Forward then backward traversal = head to tail, tail to head [OK]

Hint: Use head-to-tail then tail-to-head for full traversal [OK]

Common Mistakes:

• Trying to traverse backward without tail pointer
• Traversing forward twice instead of backward
• Assuming singly linked list can traverse backward