Java Software Solutions, 8e, Global Edition
Exercise Solutions, Ch. 13
Chapter 13 Exercise Solutions
EX 13.1. Suppose current is a reference to a Node object and that it currently
refers to a specific node in a linked list. Show, in pseudocode, the steps that would
delete the node following current from the list. Carefully consider the cases in
which current is referring to the first and last nodes in the list.
if current.next is not null then
EX 13.2. Modify your answer to Exercise 13.1 assuming that the list was set up as a
doubly linked list, with both next and prev references.
if current.next is not null then
EX 13.3. Suppose current and newNode are references to Node objects. Assume
current currently refers to a specific node in a linked list and newNode refers to
an unattached Node object. Show, in pseudocode, the steps that would insert
newNode behind current in the list. Carefully consider the cases in which
current is referring to the first and last nodes in the list.
newNode.next = current.next;
EX 13.4. Modify your answer to Exercise 13.3 assuming that the list was set up as a
doubly linked list, with both next and prev references.
newNode.prev = current;
EX 13.5. Would the front and rear references in the header node of a linked list ever
refer to the same node? Would they ever both be null? Would one ever be null if
the other was not? Explain your answers using examples.
The front and rear references in the header node of a linked list would refer to the same
Java Software Solutions, 8th Edition Exercise Solutions, Ch. 13
EX 13.6. Show the contents of a queue after the following operations are performed.
Assume the queue is initially empty.
enqueue(45);
45
enqueue(12);
12 45
EX 13.7. In terms of the final state of a queue, does it matter how dequeue
operations are intermixed with enqueue operations? Does it matter how the
enqueue operations are intermixed among themselves? Explain using examples.
In terms of the final state of a queue, as long as the number of dequeue opertions does
Java Software Solutions, 8th Edition Exercise Solutions, Ch. 13
EX 13.8. Show the contents of a stack after the following operations are performed.
Assume the stack is initially empty.
push(45);
45
push(12);
45 12 28
pop();
45 69
push(27);
45 69 27 99
45 69 27 24
push(85);
45 69 27 24 85 16
EX 13.9. In terms of the final state of a stack, does it matter how the pop operations
are intermixed with the push operations? Does it matter how the push operations
are intermixed among themselves? Explain using examples.
Java Software Solutions, 8th Edition Exercise Solutions, Ch. 13
every time 2 integers are pushed onto the stack, one is popped. The resulting stack
contains 2, 5, and 11. This single illustration is sufficient to prove that the intermixing of
push and pop operations matters.
EX 13.10. Would a tree data structure be a good choice to represent a family tree that
shows lineage? Why or why not? Would a binary tree be a better choice? Why or
why not?
A binary tree would be a good choice to represent a family tree that shows lineage
EX 13.11. What data structure would be a good choice to represent the links between
various web sites of the World Wide Web? Give an example.
A digraph (directed graph) would be a good choice to represent the links between