Two Kinds of Lists

We can use Java’s built-in arrays to create a list of items.

int[] list = new int[]{3, 5, 7};

I use the following schematic to represent this array:

┌───┬───┬───┐
│ 3 │ 5 │ 7 │
└───┴───┴───┘

Technically speaking, the variable list is of a reference type, and it holds a reference to the array. So we can also represent it like this:

          ┌───┬───┬───┐
list ───▶ │ 3 │ 5 │ 7 │
          └───┴───┴───┘

Now let’s create a list using the ListItem class.

ListItem list = new ListItem(3);
list.next = new ListItem(5);
list.next.next = new ListItem(7);

Here is the schematic for this linked list:

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

And if we want to be more precise and include the next references, we can represent it like this:

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

Both lists hold the same three values in the same order. The difference is where the values are stored and how we get from one to the next.

In the array, the three values sit in one block, side by side. The block is a single object, and the variable list refers to that one object. Since the values are laid out next to each other in a known order, Java can compute the address of any element from the address of the block. That is why we can read the element at index 2 without reading the elements at index 0 and index 1.

In the linked list, there is no block. There are three separate ListItem objects, and Java may place them anywhere in memory. Their addresses do not indicate the order. The order is stored in the next references, and those references are the only thing that connects the items. The variable list refers to the first item only. To reach the third item, we have to follow the next reference of the first item to reach the second, and then the next reference of the second item to reach the third.

So the array can get to an element by computing an address. The linked list cannot do that. It has to follow the references.