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.