☕ DSA Java Articles

Topics › Linked List › Learn 1D LinkedList

Find the length of the Linked List

Easy TUF ID 470 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Return the number of nodes in it. The empty list (a null head) has length 0.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer. The list has no cycle, so a traversal always terminates.

Example 1

list = 1 -> 2 -> 3 -> 4 -> 5
answer = 5

Example 2

list = (empty)
answer = 0                     // a null head means no nodes

Example 3

list = 3 -> 3 -> 3
answer = 3                     // equal values are still separate nodes

The node type is the standard one with an int val and a ListNode next reference.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Approach 1: Walk and count

Intuition. Unlike an array, a linked list does not store its own size. The only way to learn how many nodes there are is to visit them. A traversal that increments a counter on every node and stops at null is the whole algorithm; it is the first “real” loop you write on a linked list and the template for every traversal after it.

Algorithm.

  1. Set count = 0 and temp = head.
  2. While temp != null: increment count and move temp to temp.next.
  3. Return count.
static int lengthIterative(ListNode head) {
    int count = 0;
    ListNode temp = head;
    while (temp != null) {
        count++;
        temp = temp.next;
    }
    return count;
}

Complexity. Time O(n): every node is visited exactly once. Space O(1): a counter and one reference.

Dry run on 1 -> 2 -> 3:

iteration temp count after
start [1] 0
1 [2] 1
2 [3] 2
3 null 3

The loop condition is checked with temp on null after the third node, so the loop ends with count = 3. On an empty list the body never runs and 0 is returned without any special case. Note that the walk uses a temporary reference temp; writing head = head.next would work inside this method (Java passes the reference by value, so the caller’s variable is safe) but it is a bad habit, because in methods that must return the list it destroys the handle you need.

Approach 2: Recursion

Intuition. A linked list has a naturally recursive shape: it is either empty, or a node followed by a smaller list. The length follows the same shape. The empty list has length 0; any other list has length 1 + (length of the rest). Writing that down directly gives a two-line function that is useful to understand because many later problems (reversing recursively, checking a palindrome, flattening) use the same decomposition.

Algorithm.

  1. If head == null, return 0.
  2. Otherwise return 1 + lengthRecursive(head.next).
static int lengthRecursive(ListNode head) {
    if (head == null) return 0;
    return 1 + lengthRecursive(head.next);
}

Complexity. Time O(n), one call per node. Space O(n) for the call stack, because each pending 1 + ... has to wait for the call below it to return.

That stack cost is the reason the iterative version is preferred in practice. The default Java thread stack comfortably handles a few thousand frames (the tests use a 5000-node list), but a list of 10^5 nodes is likely to throw StackOverflowError. Recursion here is a teaching device, not a production choice; whenever a recursive linked-list algorithm is “tail recursive”, the loop version is what you should actually write.

Approach 3: Keep the size up to date

Intuition. If the length is asked for often, paying O(n) every time is wasteful. The alternative is to store a size field alongside the head and adjust it on every insertion and deletion. Each of those operations already costs at least O(1), so adding one increment or decrement does not change their complexity, while length() drops to O(1). This is exactly how java.util.LinkedList and ArrayList work: size() is a field read.

Algorithm.

  1. Wrap the head in a small class with an int size.
  2. addFirst creates a node in front of the head and does size++.
  3. removeFirst moves the head forward and does size--, doing nothing on an empty list.
  4. length() returns size.
static class SizedList {
    ListNode head;
    int size;

    void addFirst(int val) {
        head = new ListNode(val, head);
        size++;
    }

    void removeFirst() {
        if (head == null) return;
        head = head.next;
        size--;
    }

    int length() { return size; }
}

Complexity. length() is O(1) time. addFirst and removeFirst remain O(1). Space O(1) extra for the field.

The price is an invariant to maintain: size must equal the true number of nodes after every operation. If any code path modifies the links without updating size (for example, someone splices nodes in by hand), the field silently drifts. The tests guard against this by comparing list.length() with lengthIterative(list.head) after every sequence of operations. A good rule is that the links should only ever be touched through methods of the wrapper class, so there is exactly one place where each link change and its matching size change live together.

Choosing between them

  Iterative Recursive Size field
Time per query O(n) O(n) O(1)
Extra space O(1) O(n) stack one int
Works on a bare head reference yes yes no, needs the wrapper
Risk none stack overflow on long lists stale size if links are edited directly

When a problem hands you only a ListNode head, Approach 1 is the answer. When you are designing a list class, Approach 3 is what users will expect from size(). Approach 2 is the one to understand rather than use.

Edge cases and pitfalls