Bidirectional Traversal

Problem Statement

Write a Java program that extends a doubly linked list implementation to include methods for printing the list in both forward (head to tail) and backward (tail to head) directions. The doubly linked list consists of nodes, each containing an integer value, a reference to the next node, and a reference to the previous node. The program should provide methods to traverse and print the list using the next pointers for forward direction and the prev pointers for backward direction. Test the implementation with sample doubly linked lists of varying sizes, including empty lists, single-node lists, and multi-node lists. You can visualize this as displaying a chain of numbered cards in order from the first to the last card, and then from the last to the first card, using the bidirectional links.

Input:

• A doubly linked list of integers (e.g., 1↔2↔3↔4). Output: Two strings representing the list in forward order (e.g., "1 2 3 4") and backward order (e.g., "4 3 2 1"). Constraints:
• The list size is between 0 and 10^5.
• Node values are integers in the range [-10^9, 10^9].
• The list may be empty. Example:
• Input: 1↔2↔3↔4
• Output:

  Forward: 1 2 3 4
  Backward: 4 3 2 1
  

• Input: []
• Output:

  Forward: []
  Backward: []
  

• Input: 5
• Output:

  Forward: 5
  Backward: 5
  

Pseudocode

CLASS DoublyNode
    SET value to integer
    SET next to DoublyNode (null by default)
    SET prev to DoublyNode (null by default)
ENDCLASS

FUNCTION printForward(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current is not null
        APPEND current.value to result
        IF current.next is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION printBackward(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current.next is not null
        SET current to current.next
    ENDWHILE
    WHILE current is not null
        APPEND current.value to result
        IF current.prev is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.prev
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of doubly linked lists
    FOR each testCase in testCases
        PRINT test case details
        CALL printForward(testCase.head)
        CALL printBackward(testCase.head)
        PRINT forward and backward results
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a DoublyNode class with: a. An integer value. b. A next pointer to the next node. c. A prev pointer to the previous node.
2. In printForward: a. If head is null, return "[]". b. Traverse the list using next pointers, appending each value to a StringBuilder with spaces. c. Return the string representation.
3. In printBackward: a. If head is null, return "[]". b. Traverse to the tail using next pointers. c. Traverse back using prev pointers, appending each value with spaces. d. Return the string representation.
4. In main, test with empty, single-node, and multi-node doubly linked lists, printing both forward and backward.

Java Implementation

public class BidirectionalTraversal {
    // Node class for the doubly linked list
    static class DoublyNode {
        int value;
        DoublyNode next;
        DoublyNode prev;

        DoublyNode(int value) {
            this.value = value;
            this.next = null;
            this.prev = null;
        }
    }

    // Prints the list in forward direction (head to tail)
    public String printForward(DoublyNode head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        DoublyNode current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Prints the list in backward direction (tail to head)
    public String printBackward(DoublyNode head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        DoublyNode current = head;
        // Move to tail
        while (current.next != null) {
            current = current.next;
        }
        // Traverse backward
        while (current != null) {
            result.append(current.value);
            if (current.prev != null) {
                result.append(" ");
            }
            current = current.prev;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        DoublyNode head;

        TestCase(int[] values) {
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new DoublyNode(values[0]);
            DoublyNode current = head;
            for (int i = 1; i < values.length; i++) {
                DoublyNode newNode = new DoublyNode(values[i]);
                newNode.prev = current;
                current.next = newNode;
                current = newNode;
            }
        }
    }

    // Main method to test bidirectional traversal
    public static void main(String[] args) {
        BidirectionalTraversal traverser = new BidirectionalTraversal();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3, 4}), // Multi-node list
            new TestCase(new int[]{}),           // Empty list
            new TestCase(new int[]{5}),          // Single node
            new TestCase(new int[]{1, 1, 1}),    // List with duplicates
            new TestCase(new int[]{10, 20})      // Two nodes
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Forward: " + traverser.printForward(test.head));
            System.out.println("Backward: " + traverser.printBackward(test.head) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Forward: 1 2 3 4
Backward: 4 3 2 1

Test case 2:
Forward: []
Backward: []

Test case 3:
Forward: 5
Backward: 5

Test case 4:
Forward: 1 1 1
Backward: 1 1 1

Test case 5:
Forward: 10 20
Backward: 20 10

Explanation:

• Test case 1: Forward prints 1→2→3→4, backward prints 4→3→2→1.
• Test case 2: Empty list prints "[]" for both directions.
• Test case 3: Single node 5 prints "5" for both directions.
• Test case 4: List with duplicates 1→1→1 prints "1 1 1" for both directions.
• Test case 5: Two nodes 10→20 print "10 20" forward, "20 10" backward.

How It Works

• DoublyNode: Stores an integer value, a next pointer, and a prev pointer.
• printForward:
  • Traverses from head to tail using next pointers.
  • Builds a space-separated string, returning "[]" for empty lists.
• printBackward:
  • Traverses to tail using next pointers.
  • Traverses back to head using prev pointers, building a space-separated string.
• Example Trace (Test case 1):
  • Input: 1↔2↔3↔4.
  • Forward: Traverse head=1, append 1,2,3,4 → "1 2 3 4".
  • Backward: Move to tail=4, append 4,3,2,1 → "4 3 2 1".
• Main Method: Tests multi-node, empty, single-node, duplicate, and two-node lists.

Complexity Analysis Table

Note:

• n is the number of nodes in the list.
• Time complexity: O(n) for printForward (single pass); O(n) for printBackward (two passes: to tail and back).
• Space complexity: O(n) for both (StringBuilder for output).
• Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Use the next and prev pointers in a doubly linked list to enable efficient bidirectional traversal. Test both directions to ensure prev pointers are correctly set.

⚠ Warning: Ensure null checks for next and prev pointers to avoid null pointer exceptions, especially for empty or single-node lists.