Linked Data Structures - Absolute Java - page 804

15.1 Java Linked Lists

A chain is only as strong as its weakest link.

PROVERB

A linked list is a linked data structure consisting of a single chain of nodes, each
connected to the next by a link. This is the simplest kind of linked data structure, but it
is nevertheless widely used. In this section, we give examples of linked lists and develop
techniques for defining and working with linked lists in Java.

EXAMPLE: A Simple Linked List Class

Display 15.1 is a diagram of a linked list. In the display, the nodes are the boxes. In
your Java code, a node is an object of some node class, such as the class Node1 given
in Display 15.2. Each node has a place (or places) for some data and a place to hold
a link to another node. The links are shown as arrows that point to the node they
“link” to. In Java, the links will be implemented as references to a node stored in an
instance variable of the node type.
The Node1 class is defined by specifying, among other things, an instance variable of
type Node1 that is named link . This allows each node to store a reference to another
node of the same type. There is a kind of circularity in such definitions, but this circularity
is allowed in Java. (One way to see that this definition is not logically inconsistent is to
note that we can draw pictures, or even build physical models, of our linked nodes.)
The first node, or start node, in a linked list is called the head node . If you start at
the head node, you can traverse the entire linked list, visiting each node exactly once.
As you will see shortly, in Java your code must intuitively “follow the link arrows.” In
Display 15.1 , the box labeled head is not itself the head node; it is not even a node. The
box labeled head is a variable of type Node1 that contains a reference to the first node in
the linked list—that is, a reference to the head node. The function of the variable head
is that it allows your code to find that first or head node. The variable head is declared
in the obvious way:

Node1 head;
In Java, a linked list is an object that in some sense contains all the nodes of the linked
list. Display 15.3 contains a definition of a linked list class for a linked list such as the one in
Display 15.1. Notice that a linked list object does not directly contain all the nodes in the
linked list. It contains only the instance variable head that contains a reference to the first
or head node. However, every node can be reached from this first or head node. The link
instance variable of the first and every Node1 of the linked list contains a reference to the next
Node1 in the linked list. Thus, the arrows shown in the diagram in Display 15.1 are realized
as references in Java. Each node object of a linked list contains (in its link instance variable)
a reference to another object of the class Node1 , and this other object contains a reference to
another object of the class Node1 , and so on until the end of the linked list. Thus, a linked
list object, indirectly at least, contains all the nodes in the linked list.