Traversal Forward and Backward in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Forward and Backward Traversal in Doubly Linked List

What is the output of the following Java code that traverses a doubly linked list forward and then backward?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

public class DLLTraversal {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        
        head.next = second;
        second.prev = head;
        second.next = third;
        third.prev = second;

        // Forward traversal
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.print("null\n");

        // Backward traversal
        curr = third;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.prev;
        }
        System.out.print("null\n");
    }
}

A

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

B

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

C

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

D

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

💡 Hint

Think about how the 'next' and 'prev' pointers are used in forward and backward traversal.

The forward traversal starts from head and moves using 'next' pointers printing 1 -> 2 -> 3 -> null. The backward traversal starts from the last node (third) and moves using 'prev' pointers printing 3 -> 2 -> 1 -> null.

🧠 Conceptual

intermediate

Understanding Traversal Direction in Doubly Linked List

In a doubly linked list, which pointer is used to move backward during traversal?

A prev pointer

B next pointer

C head pointer

D tail pointer

💡 Hint

Backward means going to the previous node.

The 'prev' pointer in a doubly linked list points to the previous node, allowing backward traversal.

🔧 Debug

advanced

Identify the Error in Backward Traversal Code

What error will occur when running this backward traversal code snippet on a doubly linked list?

DSA Java

Node curr = head;
while (curr != null) {
    curr = curr.prev;
    System.out.print(curr.data + " -> ");
}
System.out.print("null\n");

A No error, prints list backward correctly

B Infinite loop because curr never becomes null

C Syntax error due to missing semicolon

D NullPointerException at curr.prev when curr is head

💡 Hint

Consider what happens when you try to access prev of the head node.

The head node's prev pointer is null. Accessing curr.prev when curr is head leads to NullPointerException.

❓ Predict Output

advanced

Output After Mixed Forward and Backward Traversal

What is the output of this Java code that traverses forward two nodes and then backward one node in a doubly linked list?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

public class MixedTraversal {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node second = new Node(20);
        Node third = new Node(30);
        
        head.next = second;
        second.prev = head;
        second.next = third;
        third.prev = second;

        Node curr = head;
        System.out.print(curr.data + " -> ");
        curr = curr.next;
        System.out.print(curr.data + " -> ");
        curr = curr.next;
        System.out.print(curr.data + " -> ");

        curr = curr.prev;
        System.out.print(curr.data + " -> ");

        System.out.print("null\n");
    }
}

A 10 -> 20 -> 30 -> 30 -> null

B 10 -> 20 -> 30 -> 10 -> null

C 10 -> 20 -> 30 -> 20 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

Trace the pointer moves carefully step by step.

The code prints 10, then moves next to 20, prints 20, moves next to 30, prints 30, then moves prev to 20 and prints 20 again before printing null.

🧠 Conceptual

expert

Why is Backward Traversal Useful in Doubly Linked Lists?

Which of the following is the best reason why backward traversal is useful in doubly linked lists?

A It reduces the memory used by the list nodes

B It allows efficient reverse iteration without extra memory

C It makes the list sorted automatically

D It prevents the list from having cycles

💡 Hint

Think about what backward traversal enables compared to singly linked lists.

Backward traversal allows moving from tail to head efficiently without extra data structures or memory.

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