Java Reference
In-Depth Information
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 con-
nected 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
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
Node1
type.
node
The
class is defined by specifying, among other things, an instance variable of
Node1
. 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 circular-
ity 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 in Java code shortly, your code must intuitively “follow the link
arrows.” In Display 15.1 the box labeled
type
that is named
Node1
link
is not itself the head node; it is not even
head
a node. The box labeled
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
is a variable of type
head
Node1
is that it allows your code to find that first or head node. The variable
head
is declared in the obvious way:
head
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 like the one in
Display 15.1. Notice that a linked list object does not directly contain all the nodes in the
linked list. It only contains the instance variable
that contains a reference to the first or
head node. However, every node can be reached from this first or head node. The
head
link
instance variable of the first and every
of the linked list contains a reference to the
Node1
next
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
Node1
instance
link
variable) a reference to another object of the class
, and this other object contains a
Node1
reference to another object of the class
, 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.
Node1
