Java Reference
In-Depth Information
memory system. Often the limits are much smaller, because the computer's available
memory must be shared among many applications.
The declaration and class-instance-creation expression
// 10 is nodeToAdd's data
Node<Integer> nodeToAdd =
new
Node<Integer>(
10
);
allocates a
Node<Integer>
object and returns a reference to it, which is assigned to
node-
ToAdd
. If
insufficient memory
is available, the preceding expression throws an
OutOfMemory-
Error
. The sections that follow discuss lists, stacks, queues and trees—all of which use
dynamic memory allocation and self-referential classes to create dynamic data structures.
A linked list is a linear collection (i.e., a sequence) of self-referential-class objects, called
nodes
,
connected by reference
links
—hence, the term “linked” list. Typically, a program
accesses a linked list via a reference to its first node. The program accesses each subsequent
node via the link reference stored in the previous node. By convention, the link reference
in the last node of the list is set to
null
to indicate “end of list.” Data is stored in and re-
moved from linked lists dynamically—the program creates and deletes nodes as necessary.
Stacks and queues are also linear data structures and, as we'll see, are constrained versions
of linked lists. Trees are
nonlinear
data structures.
Lists of data can be stored in conventional Java arrays, but linked lists provide several
advantages. A linked list is appropriate when the number of data elements to be repre-
sented in the data structure is
unpredictable
. Linked lists are dynamic, so the length of a list
can increase or decrease as necessary, whereas the size of a conventional Java array cannot
be altered—it's fixed when the program creates the array. [Of course,
ArrayList
s
can
grow
and shrink.] Conventional arrays can become full. Linked lists become full only when the
system has
insufficient memory
to satisfy dynamic storage allocation requests. Package
java.util
contains class
LinkedList
(discussed in Chapter 16) for implementing and
manipulating linked lists that grow and shrink during program execution.
Performance Tip 21.1
Insertion into a linked list is fast—only two references have to be modified (after locating
the insertion point). All existing node objects remain at their current locations in memory.
Linked lists can be maintained in sorted order simply by inserting each new element
at the proper point in the list. (It does, of course, take time to
locate
the proper insertion
point.)
Existing list elements do not need to be moved.
Performance Tip 21.2
Insertion and deletion in a sorted array can be time consuming—all the elements follow-
ing the inserted or deleted element must be shifted appropriately.
Linked list nodes normally are
not stored contiguously
in memory. Rather, they're logically
contiguous. Figure 21.2 illustrates a linked list with several nodes. This diagram presents
a
singly linked list
—each node contains one reference to the next node in the list. Often,
