Counting List Length by Walking

Try This First

You have a linked list whose Node<T> objects have a .next field, and whose list class has only a head reference, no size field. Write a method that returns the number of nodes.

Give it a try before reading further.

public int size() {
    int count = 0;
    for (Node<T> cur = head; cur != null; cur = cur.next) {
        count++;
    }
    return count;
}

What You Need To Walk In With

• A linked list without a size field must compute its length by visiting every node one time.
• The standard pattern is a counter accumulator combined with a traversal loop: int count = 0; for (Node<T> cur = head; cur != null; cur = cur.next) count++;
• The empty-list case is handled automatically: when head is null the loop body never runs and the method returns 0.
• Walking the entire list to get the length costs O(n) time, which is why S20 Lab 5 tracks size in a field instead (making size() O(1)).
• Every mutation method (add, remove) must update the cached size field to keep it honest. (Liang 10e Ch 24)

How It Works

When a list class tracks size as a field, calling size() is a single field read. When no field exists, you have to count by hand.

The counter-accumulator pattern uses two variables:

• cur is the traversal pointer, initialized to head.
• count is the accumulator, initialized to 0.

Each loop iteration increments count by one and advances cur to the next node. The loop stops when cur is null, meaning there are no more nodes.

// Generic linked list, no size field, no dummy head
public int size() {
    int count = 0;
    Node<T> cur = head;          // start at first real node
    while (cur != null) {
        count++;                 // tally this node
        cur = cur.next;          // advance
    }
    return count;
}

A pointer sketch for a three-node list (A -> B -> C -> null):

head
 |
[A | next] -> [B | next] -> [C | next] -> null
  cur=A         cur=B         cur=C        cur=null: loop ends
  count=1       count=2       count=3      return 3

The empty list (head == null) works without any special case: cur starts as null, the loop condition is false from the start, and the method returns 0 immediately.

Worked Example: Predict, Then Check

A list contains three elements. Someone calls size(). Trace the loop variable count at the end of each iteration.

After iteration 1, what is count? After iteration 2, what is count? After iteration 3, what is count? What does the method return?

A Common Mistake

Suppose the list class already has a size field that every mutation method updates carefully. A developer writes size() to walk the list anyway, counting nodes from scratch each time.

This works correctly but throws away free information: the field is always current, so reading it is O(1). Walking for the count costs O(n) and does the same work the mutation methods already did. The fix is straightforward: trust the bookkeeping and return the field directly.

// Correct when a size field is maintained
public int size() {
    return size;   // O(1), not O(n)
}

The walking version is only correct as the primary implementation when no size field exists, or as a temporary sanity check during debugging. (Source: Liang 10e Ch 24)

Go Deeper (optional)

The walking count generalizes naturally to recursion. The recursive form is size(node) = (node == null) ? 0 : 1 + size(node.next), which the recursion material covers in depth. Both forms visit every node once and share the O(n) cost. The iterative version here is the one to reach for first: it is easier to read, avoids stack frames, and makes the pointer motion visible step by step.

Check Yourself

Close the notes and answer each one from memory, then reveal it. Pulling an idea back from memory is one of the strongest ways to make it stick.