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.