Java Reference
In-Depth Information
linked lists are implemented as
doubly linked lists
—each node contains a reference to the
next node in the list
and
a reference to the preceding one.
Performance Tip 21.3
The elements of an array are contiguous in memory. This allows immediate access to any
array element, because its address can be calculated directly as its offset from the beginning
of the array. Linked lists do not afford such immediate access—an element can be accessed
only by traversing the list from the front (or the back in a doubly linked list).
firstNode
lastNode
...
H
D
Q
Fig. 21.2
|
Linked-list graphical representation.
The program of Figs. 21.3-21.5 uses an object of our generic
List
class to manipulate a
list of miscellaneous objects. The program consists of four classes—
ListNode
(Fig. 21.3,
lines 6-37),
List
(Fig. 21.3, lines 40-147),
EmptyListException
(Fig. 21.4) and
List-
Test
(Fig. 21.5). Encapsulated in each
List
object is a linked list of
ListNode
objects.
[
Note:
The
List
,
ListNode
and
EmptyListException
classes are placed in the package
com.deitel.datastructures
, so that they can be reused throughout this chapter. In
Section 21.4.10, we discuss the
package
statement (line 3 of Figs. 21.3 and 21.4), and
show how to compile and run programs that use classes in your own packages.]
1
// Fig. 21.3: List.java
2
// ListNode and List class declarations.
3
4
5
package
com.deitel.datastructures;
// class to represent one node in a list
6
class
ListNode<T>
7
{
8
// package access members; List can access these directly
9
T data;
// data for this node
10
ListNode<T> nextNode;
// reference to the next node in the list
11
12
// constructor creates a ListNode that refers to object
13
ListNode(T object)
14
{
15
this
(object,
null
);
16
}
17
Fig. 21.3
|
ListNode
and
List
class declarations. (Part 1 of 4.)
