The Size of a List

Another common operation is to ask how many items are in the list. Let’s write an operation called size that returns the number of items.

public static int size(ListItem head) {
  // TODO
}

A linked list does not keep a count of its items the way an array keeps its length. All we have is its head. There is no head.length we can return. So we have to count them, one by one, as we traverse the list.

public static int size(ListItem head) {
  int count = 0;
  ListItem current = head;
  while (current != null) {
    count++;
    current = current.next;
  }
  return count;
}

This is the same traversal we saw in the previous section. Instead of printing each item, we count it. We keep a counter and add one to it for every item we visit.

This process is $O(n)$, unlike the array’s length property, which returns the size in $O(1)$. size has to traverse the entire list, visiting every item to get the count.

What happens if we call size with a null head? It returns 0. The loop is never entered, so the counter is never incremented, and the method returns 0.