Traversal Forward and Backward in DSA Java - Build from Scratch

Traversal Forward and Backward

📖 Scenario: You have a list of daily temperatures recorded in a week. You want to look at these temperatures both from the start of the week to the end and then from the end of the week back to the start.

🎯 Goal: Build a Java program that stores the temperatures in an array, then prints them forward (start to end) and backward (end to start) to understand how to traverse arrays in both directions.

📋 What You'll Learn

Create an integer array called temperatures with exactly these values: 23, 25, 22, 20, 24, 26, 21

Create an integer variable called length that stores the length of the temperatures array

Use a for loop with variable i to traverse the temperatures array forward from index 0 to length - 1

Use a for loop with variable i to traverse the temperatures array backward from index length - 1 to 0

Print the temperatures in forward order separated by spaces on one line

Print the temperatures in backward order separated by spaces on the next line

💡 Why This Matters

🌍 Real World

Looking at data in both forward and backward order helps in many real-world tasks like analyzing trends over time or reversing sequences.

💼 Career

Understanding how to traverse arrays forward and backward is a fundamental skill for software developers working with data structures and algorithms.

1

Create the temperatures array

Create an integer array called temperatures with these exact values: 23, 25, 22, 20, 24, 26, 21

DSA Java

# Create the temperatures array with the given values
# Your code here

Hint

Use curly braces {} to list the values inside the array.

2

Create the length variable

Create an integer variable called length and set it to the length of the temperatures array using temperatures.length

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] temperatures = {23, 25, 22, 20, 24, 26, 21};
        // Create length variable here
        // Your code here
    }
}

Hint

Use temperatures.length to get the number of elements in the array.

3

Traverse forward and backward

Use a for loop with variable i to traverse the temperatures array forward from index 0 to length - 1 and print each temperature followed by a space. Then use another for loop with variable i to traverse the temperatures array backward from index length - 1 to 0 and print each temperature followed by a space.

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] temperatures = {23, 25, 22, 20, 24, 26, 21};
        int length = temperatures.length;
        // Traverse forward and print temperatures
        // Your code here
        
        // Traverse backward and print temperatures
        // Your code here
    }
}

Hint

Use two separate for loops: one counting up from 0 to length - 1, and one counting down from length - 1 to 0.

4

Print the final output

Add a System.out.println() after the forward traversal loop to move to the next line before printing the backward traversal. This will print the temperatures forward on one line and backward on the next line.

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] temperatures = {23, 25, 22, 20, 24, 26, 21};
        int length = temperatures.length;
        for (int i = 0; i = 0; i--) {
            System.out.print(temperatures[i] + " ");
        }
    }
}

Hint

Use System.out.println() with no arguments to move to the next line.

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