A Linked List Is Recursive

So far we have used the word recursion for methods: a method is recursive when it calls itself. Data can be recursive too. The simplest example is the linked list.

Earlier in the course we built a list without an array, as a linked list of Node objects. Each node holds a value and a next reference to the node after it, and the last node’s next is null:

private static class Node<T> {
  T value;
  Node<T> next;
}

Here is a list of three values:

         ┌───┐     ┌───┐     ┌───┐
head ──▶ │ 3 │ ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
         └───┘     └───┘     └───┘

Now look at what next points to. It points to another Node, the head of the rest of the list. And the rest of the list is itself a shorter linked list:

         ┌───┐     ┌───┐
...  ──▶ │ 5 │ ──▶ │ 7 │ ──▶ null
         └───┘     └───┘

The list 5 ──▶ 7 ──▶ null is a linked list, and so are 7 ──▶ null and null, the empty list. The whole list is just the value 3 placed in front of one of these smaller lists.

So a linked list is one of two things:

• the empty list, written null, or
• a node holding a value, followed by a linked list.

The definition mentions a linked list inside its own description, in the second case. That is not a mistake. A recursive method does the same thing: its body calls the method on a smaller input. The empty list is where the definition stops, so it plays the role of a base case. The second case reduces a list to a value plus a smaller list, which is what a recursive case does to a problem.

This is what we mean by a recursive data structure: a structure defined in terms of a smaller version of itself. Each node is followed by exactly one smaller list. That is the same shape as the call tree of factorial, which is a single chain because each call makes one call below it.