Java Reference
In-Depth Information
The available nodes are not allocated all at once the way locations are allocated for an array.
Initially there are no available nodes; we allocate a node each time we add a new entry to the queue.
However, when we remove an entry from the queue, we keep its node in the circle of nodes rather
than deallocating it. Thus, a subsequent addition to the queue uses a node from the chain of avail-
able nodes. But if no such node is available, we allocate a new one and link it into the chain.
11.26
Detecting an empty queue or an absence of available nodes is easier if one node in the circular linked
chain is unused. The situation is analogous to the circular array that we used in Segment 11.10.
Figure 11-14a shows the queue when it is empty. Both
queueNode
and
freeNode
reference the same
unused node. Notice that the node references itself. We can tell that the queue is empty because
queueNode
equals
freeNode
.
To add an entry to this empty queue, we allocate a new node and link it into the circular chain.
Figure 11-14b shows the resulting chain for a queue of one entry. To simplify the figure, we have
not illustrated the actual object in the queue. Although a node in the chain references an object in
the queue, we will sometimes say that the node is in the queue.
While
queueNode
references the node assigned to the queue,
freeNode
still references the
unused node. After three more additions to the queue, three more nodes are allocated and linked
into the chain. Segment 11.28 will describe exactly how to accomplish this. The chain now appears
as in Figure 11-14c. Again,
freeNode
references the unused node. Since
queueNode
references the
node at the front of the queue, retrieving the front entry is easy.
FIGURE 11-14
A two-part circular linked chain that represents a queue: (a) when it is
empty; (b) after adding one entry; (c) after adding three more entries;
(d) after removing the front entry; (e) after adding one more entry
queueNode
(a)
(b)
(c)
queueNode
freeNode
queueNode
freeNode
freeNode
freeNode
(d)
(e)
Node previously at the
front of the queue
queueNode
queueNode
freeNode
New entry is in
this node