Java Reference
In-Depth Information
15
Linked Data Structures
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
, that are con-
node and link
nected via things called
. 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
links
linked list
. A sample linked list can be depicted as shown in Display 15.1. In Dis-
play 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
reflects 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
linked list
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 program-
ming 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
head node
package. It makes
sense to use this library class, since it is well designed, 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.
library class as part of the
LinkedList
java.util
