Linked List Traversal

Problem Statement

Write a Java program that implements both recursive and iterative methods to traverse and print the elements of a singly linked list. The program should take a singly linked list as input and print each element in order, from the head to the tail. Test both approaches with lists of varying sizes, including empty lists and single-node lists, and discuss their trade-offs in terms of readability, performance, and memory usage. You can visualize this as walking through a chain of boxes, each containing a number, and reading the numbers either by stepping through each box (iterative) or by recursively passing to the next box (recursive).

Input: A singly linked list with integer nodes (e.g., 1 -> 2 -> 3 -> null). Output: The elements of the list printed in order, each on a new line (e.g., 1, 2, 3). Constraints:

• The list contains 0 to 10^5 nodes.
• Node values are integers between -10^9 and 10^9.
• The list may be empty. Example:
• Input: Linked list 1 -> 2 -> 3 -> null
• Output:

  1
  2
  3
  

• Explanation: The elements 1, 2, and 3 are printed in order.
• Input: Empty linked list null
• Output: (no output)
• Explanation: An empty list has no elements to print.

Pseudocode

FUNCTION recursivePrint(node)
    IF node is null THEN
        RETURN
    ENDIF
    PRINT node.value
    CALL recursivePrint(node.next)
ENDFUNCTION

FUNCTION iterativePrint(node)
    SET current to node
    WHILE current is not null
        PRINT current.value
        SET current to current.next
    ENDWHILE
ENDFUNCTION

FUNCTION mainPrint(head)
    CALL recursivePrint(head)
    CALL iterativePrint(head)
ENDFUNCTION

Algorithm Steps

1. For the recursive approach: a. Check if the current node is null. If so, return, as there are no more elements to print. b. Define a recursive function that takes the current node as a parameter. c. Print the value of the current node. d. Recursively call the function on the next node in the list.
2. For the iterative approach: a. Initialize a pointer current to the head of the list. b. While current is not null, print the value of current and move current to the next node.
3. In the main function, call both the recursive and iterative methods to print the list’s elements.
4. Discuss trade-offs: recursive is more concise but uses more memory due to the call stack; iterative is less readable but more space-efficient.

Java Implementation

public class LinkedListTraversal {
    // Node class for singly linked list
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Prints linked list using recursion
    public void recursivePrint(Node head) {
        // Base case: if node is null, stop
        if (head == null) {
            return;
        }
        // Print current node's data
        System.out.println(head.data);
        // Recursive call for next node
        recursivePrint(head.next);
    }

    // Prints linked list using iteration
    public void iterativePrint(Node head) {
        // Start at head
        Node current = head;
        // Iterate until null
        while (current != null) {
            // Print current node's data
            System.out.println(current.data);
            // Move to next node
            current = current.next;
        }
    }
}

Output

For the input linked list 1 -> 2 -> 3 -> null, both methods output:

1
2
3

Explanation: The elements 1, 2, and 3 are printed in order from head to tail.

For an empty linked list null, both methods output:

(nothing printed)

Explanation: An empty list has no elements to print.

For a single-node linked list 4 -> null, both methods output:

4

Explanation: The single node’s value 4 is printed.

How It Works

• Recursive Approach:
  • Step 1: The recursivePrint method checks if the head is null. For 1 -> 2 -> 3 -> null, it proceeds.
  • Step 2: Recursion:
    • For node 1: Print 1, recurse on node 2.
    • For node 2: Print 2, recurse on node 3.
    • For node 3: Print 3, recurse on null.
    • For null: Base case, return.
  • Example Trace: For 1 -> 2 -> 3 -> null, prints 1, then 2, then 3.
• Iterative Approach:
  • Step 1: The iterativePrint method initializes current to the head (1).
  • Step 2: Iterates:
    • current = 1: Print 1, move to 2.
    • current = 2: Print 2, move to 3.
    • current = 3: Print 3, move to null.
    • current = null: Stop.
  • Example Trace: For 1 -> 2 -> 3 -> null, prints 1, 2, 3 in sequence.
• Trade-offs:
  • Readability: Recursive is more concise and elegant, mirroring the list’s structure, but may be harder for beginners to grasp.
  • Performance: Both have O(n) time, but recursive uses O(n) space due to the call stack, while iterative uses O(1) space, making it more efficient for large lists.
  • Memory: Recursive risks stack overflow for very large lists; iterative is safer.

Complexity Analysis Table

Note:

• n is the number of nodes in the linked list.
• Time complexity: O(n) for both, as each node is visited exactly once.
• Space complexity: O(n) for recursive due to the call stack; O(1) for iterative, using only a single pointer.
• Best, average, and worst cases are O(n) for both.

✅ Tip: Use the iterative approach for large linked lists to avoid stack overflow and minimize memory usage. Test with empty lists and long lists to verify correctness and compare performance.

⚠ Warning: The recursive approach may cause stack overflow for very large lists (e.g., 10^5 nodes) due to O(n) space complexity. Ensure the list is properly constructed to avoid null pointer exceptions.