Traversal Forward and Backward in DSA Java

Mental Model

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

Analogy: Imagine reading a book: reading pages from the first to the last is forward traversal, and flipping back from the last page to the first is backward traversal.

Head -> 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑ (start)
Tail -> 4 ↔ 3 ↔ 2 ↔ 1 -> null
↑ (end)

Dry Run Walkthrough

Input: Doubly linked list: 1 ↔ 2 ↔ 3 ↔ 4, traverse forward then backward

Goal: Visit all nodes from start to end, then from end back to start, printing their values

Step 1: Start at head node with value 1 for forward traversal

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

Why: We begin traversal from the first node

Step 2: Print 1, move curr to next node 2

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

Why: Visit next node to continue forward traversal

Step 3: Print 2, move curr to next node 3

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

Why: Keep moving forward through the list

Step 4: Print 3, move curr to next node 4

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

Why: Reach the last node in forward traversal

Step 5: Print 4, forward traversal ends, start backward traversal at tail node 4

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

Why: Backward traversal starts from the last node

Step 6: Print 4, move curr to previous node 3

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

Why: Move backward to visit previous nodes

Step 7: Print 3, move curr to previous node 2

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

Why: Continue backward traversal

Step 8: Print 2, move curr to previous node 1

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

Why: Reach the first node again in backward traversal

Step 9: Print 1, backward traversal ends

null ← 1 ← 2 ← 3 ← 4

Why: Traversal complete in both directions

Result:

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

Annotated Code

DSA Java

class Node {
    int data;
    Node next;
    Node prev;

    Node(int data) {
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}

public class DoublyLinkedListTraversal {
    Node head;
    Node tail;

    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
            return;
        }
        tail.next = newNode; // link current tail to new node
        newNode.prev = tail; // link new node back to current tail
        tail = newNode; // update tail to new node
    }

    void traverseForward() {
        Node curr = head; // start at head
        while (curr != null) {
            System.out.print(curr.data + " -> "); // print current node
            curr = curr.next; // move forward
        }
        System.out.println("null");
    }

    void traverseBackward() {
        Node curr = tail; // start at tail
        while (curr != null) {
            System.out.print(curr.data + " -> "); // print current node
            curr = curr.prev; // move backward
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        DoublyLinkedListTraversal dll = new DoublyLinkedListTraversal();
        dll.append(1);
        dll.append(2);
        dll.append(3);
        dll.append(4);

        dll.traverseForward();
        dll.traverseBackward();
    }
}

tail.next = newNode; // link current tail to new node

connect new node after current tail to extend list forward

newNode.prev = tail; // link new node back to current tail

connect new node back to tail for backward traversal

tail = newNode; // update tail to new node

update tail pointer to new last node

Node curr = head; // start at head

begin forward traversal from first node

curr = curr.next; // move forward

advance to next node in forward direction

Node curr = tail; // start at tail

begin backward traversal from last node

curr = curr.prev; // move backward

advance to previous node in backward direction

Output

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

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

Complexity Analysis

Time: O(n) because we visit each of the n nodes once in each traversal direction

Space: O(1) because traversal uses only a few pointers, no extra space grows with input size

vs Alternative: Compared to singly linked list forward-only traversal, doubly linked list allows backward traversal without extra work

Edge Cases

Empty list

No nodes to traverse; traversal prints only 'null'

DSA Java

while (curr != null) { ... }

Single node list

Forward and backward traversal print the single node once

DSA Java

while (curr != null) { ... }

When to Use This Pattern

When you need to visit elements in both directions efficiently, look for doubly linked list traversal patterns because they allow forward and backward moves easily.

Common Mistakes

Mistake: Trying to traverse backward in a singly linked list without a prev pointer
Fix: Use a doubly linked list that stores prev pointers to enable backward traversal

Mistake: Not updating tail pointer when appending nodes
Fix: Always update tail to the new node after appending to keep track of list end

Summary

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

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

The key is that each node links to both next and previous nodes, enabling two-way movement.

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