Traversal Forward and Backward in DSA Python

Mental Model

Traversal means visiting each item in a list one by one, either from start to end or end to start.

Analogy: Imagine walking through a row of houses on a street. Going forward means walking from the first house to the last. Going backward means walking back from the last house to the first.

Head -> 1 -> 2 -> 3 -> 4 -> null
Tail ← 1 ← 2 ← 3 ← 4 ← null
↑ Forward pointer at 1
↑ Backward pointer at 4

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4, traverse forward and backward

Goal: Visit and print all nodes from start to end, then from end to start

Step 1: Start at head node for forward traversal

1 [curr->] -> 2 -> 3 -> 4 -> null

Why: We begin visiting nodes from the first node

Step 2: Move forward pointer to next node

1 -> 2 [curr->] -> 3 -> 4 -> null

Why: Visit nodes one by one in forward direction

Step 3: Continue moving forward pointer

1 -> 2 -> 3 [curr->] -> 4 -> null

Why: Keep visiting nodes until the end

Step 4: Move forward pointer to last node

1 -> 2 -> 3 -> 4 [curr->] -> null

Why: Last node reached, forward traversal done

Step 5: Start backward traversal from tail node

1 ← 2 ← 3 ← 4 [curr←] ← null

Why: Begin visiting nodes from last node backward

Step 6: Move backward pointer to previous node

1 ← 2 ← 3 [curr←] ← 4 ← null

Why: Visit nodes one by one in backward direction

Step 7: Continue moving backward pointer

1 ← 2 [curr←] ← 3 ← 4 ← null

Why: Keep visiting nodes until the start

Step 8: Move backward pointer to first node

1 [curr←] ← 2 ← 3 ← 4 ← null

Why: First node reached, backward traversal done

Result:

Forward traversal: 1 -> 2 -> 3 -> 4 -> null
Backward traversal: 4 -> 3 -> 2 -> 1 -> null

Annotated Code

DSA Python

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def traverse_forward(self):
        curr = self.head
        while curr:
            print(curr.val, end=' -> ')
            curr = curr.next
        print('null')

    def traverse_backward(self):
        curr = self.tail
        while curr:
            print(curr.val, end=' -> ')
            curr = curr.prev
        print('null')

# Driver code
list_dll = DoublyLinkedList()
for value in [1, 2, 3, 4]:
    list_dll.append(value)

list_dll.traverse_forward()
list_dll.traverse_backward()

curr = self.head

start forward traversal from head node

while curr:

loop until end of list reached

curr = curr.next

advance forward pointer to next node

curr = self.tail

start backward traversal from tail node

while curr:

loop until start of list reached

curr = curr.prev

advance backward pointer to previous node

Output

1 -> 2 -> 3 -> 4 -> null

4 -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because each node is visited once in forward and once in backward traversal

Space: O(1) because traversal uses only pointers without extra storage

vs Alternative: Compared to singly linked list, backward traversal is not possible without extra memory or reversing the list

Edge Cases

empty list

no output except 'null' for both traversals

DSA Python

while curr:

single node list

forward and backward traversal print the single node once

DSA Python

while curr:

When to Use This Pattern

When you need to visit all elements in order and reverse order in a list, use traversal forward and backward on a doubly linked list because it supports moving both ways easily.

Common Mistakes

Mistake: Trying to traverse backward on a singly linked list without extra steps
Fix: Use a doubly linked list that has previous pointers to move backward

Mistake: Not updating the tail pointer when appending nodes
Fix: Always update tail to the new last node after append

Summary

It visits each node from start to end and then from end to start in a doubly linked list.

Use it when you want to read or process data in both forward and backward order efficiently.

The key is that each node links to both next and previous nodes, allowing easy movement both ways.

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