Java Reference
In-Depth Information
FIGURE 11-12
A circular linked chain with an external reference to its last node
that (a) has more than one node; (b) has one node; (c) is empty
(a)
(b)
(c)
lastNode
lastNode
lastNode
When a linked chain—whether it is linear or circular—represents a queue, it has one node for each
entry in the queue. When we add an entry to the queue, we allocate a new node for the chain. When
we remove an entry from the queue, a node is deallocated.
In the circular array implementation, the queue uses a subset of the fixed number of array
locations available. When we add an entry to the queue, we use the next unoccupied location in
the array. When we remove an entry from the queue, we make its array location available for the
queue's later use. Since additions and removals are at the ends of a queue, the queue occupies
contiguous locations in the circular array. The available locations also are contiguous, again
because the array is circular. Thus, the circular array has two parts: One part contains the queue
and the other part is available for the queue.
Suppose that we had two parts in a circular linked chain. The linked nodes that form the
queue are followed by linked nodes that are available for use in the queue, as Figure 11-13 illus-
trates. Here
queueNode
references the node assigned to the front of the queue;
freeNode
refer-
ences the first available node that follows the end of the queue. You could think of this
configuration as two chains—one for the queue and one for the available nodes—that are joined
at their ends to form a circle.
FIGURE 11-13
A two-part circular linked chain that represents both a queue
and the nodes available to the queue
freeNode
queueNode
