Stacks and queues - Data Structures and Problem Solving Using Java - page 606

The advantage of the linked list is that the excess memory is only one ref-
erence per item. In contrast, a contiguous array implementation uses excess
space equal to the number of vacant array items (plus some additional mem-
ory during the doubling phase). The linked list advantage can be significant in
other languages if the vacant array items store uninitialized instances of
objects that consume significant space. In Java this advantage is minimal.
Even so, we discuss the linked list implementations for three reasons.

The advantage of a
linked list imple-
mentation is that
the excess memory
is only one refer-
ence per item. The
disadvantage is that
the memory man-
agement could be
time consuming.

1. An understanding of implementations that might be useful in other

languages is important.

2. Implementations that use linked lists can be shorter for the queue than

the comparable array versions.

3. These implementations illustrate the principles behind the more gen-

eral linked list operations given in Chapter 17.

For the implementation to be competitive with contiguous array imple-
mentations, we must be able to perform the basic linked list operations in con-
stant time. Doing so is easy because the changes in the linked list are
restricted to the elements at the two ends (front and back) of the list.

16.2.1 stacks

The stack class can be implemented as a linked list in which the top of the stack
is represented by the first item in the list, as shown in Figure 16.18. To imple-
ment a push , we create a new node in the list and attach it as the new first ele-
ment. To implement a pop , we merely advance the top of the stack to the second
item in the list (if there is one). An empty stack is represented by an empty
linked list. Clearly, each operation is performed in constant time because, by
restricting operations to the first node, we have made all calculations indepen-
dent of the size of the list. All that remains is the Java implementation.
Figure 16.19 provides the class skeleton. Lines 39 to 49 give the type
declaration for the nodes in the list. A ListNode consists of two data members:

In implementing the
stack class, the top
of the stack is rep-
resented by the
first item in a linked
list.

figure 16.18
Linked list
implementation of the
Stack class

topOfStack

D C B A