Java Illuminated, 5th Edition

14.12 Recursively Defined Linked Lists

A linked list can be defined recursively. A recursively defined linked list is made up of two items:

• first, an item, which is the first item in the linked list

• rest, a linked list, which consists of the rest of the linked list

Figure 14.25 shows a representation of a recursively defined linked list.

In our recursively defined linked list, we have two instance variables: the item first and the linked list rest. Because we can access the rest of the list through the rest instance variable, we do not need a node class.

In designing our class encapsulating a recursive linked list of generic objects, we will limit ourselves to an unsorted linked list. We will insert at the beginning of the list. When we ...