Java Reference
In-Depth Information
never duplicated, then this additional space adds unnecessary overhead. Java most
naturally stores references to objects, meaning that only a single copy of an object
such as a payroll record will be maintained, even if it is on multiple lists.
Whether it is more advantageous to use references to shared elements or sepa-
rate copies depends on the intended application. In general, the larger the elements
and the more they are duplicated, the more likely that references to shared elements
is the better approach.
A second issue faced by implementors of a list class (or any other data structure
that stores a collection of user-defined data elements) is whether the elements stored
are all required to be of the same type. This is known as homogeneity in a data
structure. In some applications, the user would like to define the class of the data
element that is stored on a given list, and then never permit objects of a different
class to be stored on that same list. In other applications, the user would like to
permit the objects stored on a single list to be of differing types.
For the list implementations presented in this section, the compiler requires that
all objects stored on the list be of the same type. Besides Java generics, there are
other techniques that implementors of a list class can use to ensure that the element
type for a given list remains fixed, while still permitting different lists to store
different element types. One approach is to store an object of the appropriate type
in the header node of the list (perhaps an object of the appropriate type is supplied
as a parameter to the list constructor), and then check that all insert operations on
that list use the same element type.
The third issue that users of the list implementations must face is primarily of
concern when programming in languages that do not support automatic garbage
collection. That is how to deal with the memory of the objects stored on the list
when the list is deleted or the
clear
method is called. The list destructor and the
clear
method are problematic in that there is a potential that they will be misused.
Deleting
listArray
in the array-based implementation, or deleting a link node
in the linked list implementation, might remove the only reference to an object,
leaving its memory space inaccessible. Unfortunately, there is no way for the list
implementation to know whether a given object is pointed to in another part of the
program or not. Thus, the user of the list must be responsible for deleting these
objects when that is appropriate.
4.1.5
Doubly Linked Lists
The singly linked list presented in Section 4.1.2 allows for direct access from a
list node only to the next node in the list. A doubly linked list allows convenient
access from a list node to the next node and also to the preceding node on the list.
The doubly linked list node accomplishes this in the obvious way by storing two
pointers: one to the node following it (as in the singly linked list), and a second
pointer to the node preceding it. The most common reason to use a doubly linked
