Traversal of Singly Linked List

Q: What does traversing a singly linked list mean?

Traversal means visiting every node once, from the head to the last node, by following the next references. It is used to print the list, count nodes, search for a value or calculate a total.

Q: Write an iterative Java method to traverse a singly linked list.

It runs in O(n) time and O(1) space. Java example: static void traverse(Node head) { Node current = head; while (current != null) { System.out.print(current.data + " -> "); current = current.next; } System.out.println("null"); }

Q: Write a recursive Java method to traverse a singly linked list.

It also runs in O(n) time, but it uses O(n) stack space, one frame per node.

Q: Why should you not move the head reference during traversal?

If you write head = head.next in the loop, you lose the reference to the first node. Inside a method this only changes the local copy, but if head is a field of the list object, the list loses its start. Always use a separate current variable.

Q: Write a Java method to count the nodes in a singly linked list.

Java example: static int count(Node head) { int count = 0; for (Node current = head; current != null; current = current.next) { count++; } return count; }

Q: Write a Java method to find the sum of all values in a linked list.

Java example: static long sum(Node head) { long total = 0; Node current = head; while (current != null) { total += current.data; current = current.next; } return total; }

Q: What happens if you traverse a list that has a cycle?

The loop while (current != null) never ends, because there is no null at the end. If a list might contain a cycle, check it first with Floyd's algorithm (slow and fast pointers).

Q: Write a Java method to find the maximum value in a linked list.

Java example: static int max(Node head) { if (head == null) { throw new IllegalArgumentException("List is empty"); } int max = head.data; for (Node current = head.next; current != null; current = current.next) { max = Math.max(max, current.data); } return max; }

Traversal of Singly Linked List

In this Linked List tutorial, we will see all about the traversal of linked list.

To traverse a linked list, there are two approaches:

Iterative Approach
Recursive Approach

Traverse a linked list using Iterative approach

TraversalUsingIterativeApproachInSLL.java

// Java program to traverse a linked list using Iterative approach
public class TraversalUsingIterativeApproachInSLL {
  // Method to traverse and print the list
  static void traverseList(Node head) {

    while (head != null) {
      // Printing data of node
      System.out.print(head.data + " -> ");
      // Moving to the next node
      head = head.next;
    }
    System.out.println("null");
  }

  public static void main(String[] args) {
    // Create a linked list
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);
    head.next.next.next.next = new Node(50);

    // Linked list will be created like this
    // 10 -> 20 -> 30 -> 40 -> 50

    // Traversing and printing the list
    traverseList(head);
  }
}

Output

10 -> 20 -> 30 -> 40 -> 50 -> null

Traverse a linked list using Recursive approach

TraversalUsingRecursiveApproachInSLL.java

// Java program to traverse a linked list using Recursive approach
public class TraversalUsingRecursiveApproachInSLL {
  // Method to traverse and print the linked list
  static void traverseList(Node head) {

    // Returns if list is empty
    if (head == null) {
      System.out.println("null");
      return;
    }

    // Printing the node data
    System.out.print(head.data + " -> ");

    // Moving to the next node
    traverseList(head.next);
  }

  public static void main(String[] args) {
    // Create a linked list
    Node head = new Node(10);
    head.next = new Node(20);
    head.next.next = new Node(30);
    head.next.next.next = new Node(40);
    head.next.next.next.next = new Node(50);

    // Linked list will be created like this
    // 10 -> 20 -> 30 -> 40 -> 50

    // Traversing and printing the list
    traverseList(head);
  }
}

Output

10 -> 20 -> 30 -> 40 -> 50 -> null

Frequently Asked Questions (FAQ)

Q1. What does traversing a singly linked list mean?

Traversal means visiting every node once, from the head to the last node, by following the next references. It is used to print the list, count nodes, search for a value or calculate a total.

Q2. Write an iterative Java method to traverse a singly linked list.

TraverseIterative.java

static void traverse(Node head) {
    Node current = head;
    while (current != null) {
        System.out.print(current.data + " -> ");
        current = current.next;
    }
    System.out.println("null");
}

It runs in O(n) time and O(1) space.

Q3. Write a recursive Java method to traverse a singly linked list.

TraverseRecursive.java

static void traverse(Node node) {
    if (node == null) {
        System.out.println("null");
        return;
    }
    System.out.print(node.data + " -> ");
    traverse(node.next);
}

It also runs in O(n) time, but it uses O(n) stack space, one frame per node.

Q4. Which is better, iterative or recursive traversal?

The iterative version is usually better in Java: it uses constant memory and cannot cause a StackOverflowError. A list with a few hundred thousand nodes can overflow the default thread stack with recursion. Recursion is shorter to write and handy for tasks such as printing in reverse.

Q5. Why should you not move the head reference during traversal?

If you write head = head.next in the loop, you lose the reference to the first node. Inside a method this only changes the local copy, but if head is a field of the list object, the list loses its start. Always use a separate current variable.

Q6. Write a Java method to count the nodes in a singly linked list.

CountNodes.java

static int count(Node head) {
    int count = 0;
    for (Node current = head; current != null; current = current.next) {
        count++;
    }
    return count;
}

Q7. Write a Java method to find the sum of all values in a linked list.

SumList.java

static long sum(Node head) {
    long total = 0;
    Node current = head;
    while (current != null) {
        total += current.data;
        current = current.next;
    }
    return total;
}

Q8. How do you print a singly linked list in reverse without changing it?

Use recursion: visit the rest of the list first, then print the current node on the way back:

PrintReverse.java

static void printReverse(Node node) {
    if (node == null) {
        return;
    }
    printReverse(node.next);
    System.out.print(node.data + " ");
}

For 1→2→3 it prints 3 2 1. A Deque used as a stack works too and avoids deep recursion.

Q9. What happens if you traverse a list that has a cycle?

The loop while (current != null) never ends, because there is no null at the end. If a list might contain a cycle, check it first with Floyd's algorithm (slow and fast pointers).

Q10. Write a Java method to find the maximum value in a linked list.

MaxValue.java

static int max(Node head) {
    if (head == null) {
        throw new IllegalArgumentException("List is empty");
    }
    int max = head.data;
    for (Node current = head.next; current != null; current = current.next) {
        max = Math.max(max, current.data);
    }
    return max;
}

Was this tutorial helpful?

Help Us Improve

Traversal of Singly Linked List

Traverse a linked list using Iterative approach

Traverse a linked list using Recursive approach

Frequently Asked Questions (FAQ)