Java Reference
In-Depth Information
15
If somebody there chanced to be
Who loved me in a manner true
My heart would point him out to me
And I would point him out to you.
GILBERT AND SULLIVAN,
Ruddigore
Introduction
A linked data structure consists of capsules of data, known as
nodes
, which are connected
via what are known as
links
. These links can be viewed as arrows and thought of as
one-way passages from one node to another. The simplest kind of linked data structure
consists of a single chain of nodes, each connected to the next by a link; this is known as a
linked list
. A sample linked list can be depicted as shown in Display 15.1 . In Display 15.1 ,
the nodes are represented by boxes that can each hold two kinds of data, a string and
an integer, as in a shopping list. The links are depicted as arrows, which reflect the
fact that your code must traverse the linked list in one direction without backing up.
So there is a first node, a second node, and so on up to the last node. The first node
is called the
head node
.
That information is all very vague but provides the general picture of what is
going on in a linked list. It becomes concrete when you realize a linked list in some
programming language. In Java, the nodes are realized as objects of a node class. The
data in a node is stored via instance variables. The links are realized as references. Recall
that a reference is simply a memory address. A reference is what is stored in a variable
of a class type. So the link is realized as an instance variable of the type of the node
class itself. In Java, a node in a linked list is connected to the next node by having an
instance variable of the node type contain a reference (that is, a memory address) of
where in memory the next node is stored.
Java comes with a
LinkedList
library class as part of the
java.util
package.
It makes sense to use this library class, because it is well designed and well tested,
and will save you a lot of work. However, using the library class will not teach you
how to implement linked data structures in Java. To do that, you need to see an
implementation of a simple linked data structure, such as a linked list. So to let you see
how this sort of thing is done in Java, we will construct our own simplified example of
a linked list.
After discussing linked lists, we then go on to discuss more elaborate linked data
structures, including sets, hash tables, and trees.
node and link
linked list
head node
