A Linked List

In the previous section, we defined a ListItem class that represents an item in a list. Each ListItem has a field to store the value of the item and a field to reference the next ListItem in the list. Let’s see how we can use the ListItem class to create a list.

We start by creating the first item:

ListItem item1 = new ListItem(5);

Here is a schematic representation of what we have so far:

               ┌────────────────────┐
   item1 ■───▶ │ ListItem           │
               │   value = 5        │
               │   next = null      │
               └────────────────────┘

Now let’s create a second item and link the first item to it:

ListItem item2 = new ListItem(3);
item1.next = item2;  // item1 points to item2

Here is the updated schematic representation:

               ┌────────────────────┐
   item1 ■───▶ │ ListItem           │
               │   value = 5        │
               │   next ■───────────┼─────┐
               └────────────────────┘     │
                                          │
                                          │
               ┌────────────────────┐     │
   item2 ■───▶ │ ListItem           │ ◀───┘
               │   value = 3        │
               │   next = null      │
               └────────────────────┘

We can further simplify the schematic by omitting the field names:

          ┌───┐     ┌───┐
item1 ──▶ │ 5 │ ──▶ │ 3 │ ──▶ null
          └───┘     └───┘

Let’s create a third item and link the second item to it:

ListItem item3 = new ListItem(7);
item2.next = item3;  // item2 points to item3

And here is an even simpler schematic representation:

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

This is a linked list. A linked list is a data structure that consists of a sequence of items, where each item points to the next item in the sequence.