A linked list is a sequence of elements arranged one after another, with each element connected to the next element by a “link.” The link to the next element is combined with each element in a component called a node. A node is represented pictorially as a box with an element written inside of the box and a link drawn as an arrow and used to connect one node to another.

Figure 29-1

In addition to connecting two nodes, the links also place the nodes in a particular order. In Figure 29-1 above, the five nodes form a chain with the first node linked to the second, the second node linked to the third node, and so on until the last node is reached. The last node is a special case since it is not linked to another node and its link is indicated with a diagonal line.

Each node contains two pieces of information: an element and a reference to another node. This can be implemented as a Java class for a node using an instance variable to hold the element, and a second instance variable that is a reference to another node as follows.

public class ListNode{
  private Object value;  // the element stored in this node
  private ListNode next; // reference to next node in List
...
}

The declaration seems circular and in some ways it is, but the compiler will allow such definitions. A ListNode will have two data members, an Object and a reference to another ListNode. The instance variable next will point to the next ListNode in a linked list.

The ListNode class is constructed so that the elements of a list are objects (i.e., have the Object data type). Since any class extends Object, you can put any kind of object into a list, including arrays and strings.

Whenever a program builds and manipulates a linked list, the nodes are accessed through one or more references to nodes. Typically, a program includes a reference to the first node (first) and a reference to the last node (last).

ListNode first;
ListNode last;

A program can create a linked list as shown below in Figure 29.2. The first and last reference variables provide access to the first and last nodes of the list.

Figure 29.2

Figure 29-2 illustrates a linked list with a reference to the first node where the list terminates at the final node (indicated by a diagonal line in the reference field of the last node). Instead of a reference to another node, the final node contains a null reference. Recall that null is a special Java constant that can be used for any reference variable that has nothing to refer to. There are several common situations where the null reference is used:

1. When a reference variable is first declared and there is not yet an object for it to refer to, it can be given an initial value of the null reference.

2. The null reference occurs in the link part of the final node of a linked list.

3. When a linked list does not yet have any nodes, the null reference is used for the first and last reference variables to indicate an empty list.