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 30-1
In addition to connecting two nodes, the links also place the nodes in a particular order. In Figure 30-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 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 proceed to create a linked list as shown below. The first
and last
reference variables provide access to the first and last nodes of the list

Figure 30-1
Figure 30-2 illustrates a linked list with a reference to the first node that 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, which is a special Java constant. The null reference can be used for any reference variable that has nothing to refer to. There are several common situations where the null reference is used:
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.
The null reference occurs in the link part of the final node of a linked list.
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.
In a program, the null reference is written as the keyword null
.