Java Software Structures, 4th Edition Exercise Solutions, Ch. 4
Chapter 4 Exercise Solutions
EX 4.1. Explain what will happen if the steps depicted in Figure 14.4 are reversed.
If we change the front reference of the list before we set the next reference of the
EX 4.2. Explain what will happen if the steps depicted in Figure 14.5 are reversed.
If we change the next reference of current before we set the next reference of the
EX 4.3. Draw a UML diagram showing the relationships among the classes involved in the
linked list implementation of a stack.
LinkedStack <<interface>>
Stack
EX 4.4. Write an algorithm for the push method that will add at the end of the list instead of
the beginning. What is the time complexity of this algorithm?
Create a new node containing a reference to the object to be placed on the
stack.
Create a current pointer that references the first element of the linked list
representing the stack.
EX 4.5. Modify the algorithm from the previous exercise so that it makes use of a rear
reference. How does this affect the time complexity of this and the other
operations?
Create a new node containing a reference to the object to be placed on the
stack.
EX 4.6. Discuss the effect on all operations on a stack if there were not a count variable in
the implementation.
Push and pop would be minimally affected. The only difference would be that the
count variable would not have to be updated. Peek would not be affected at all.
EX 4.7. Discuss the impact (and draw an example) of using a sentinel node or dummy
node at the head of a list.
A sentinel node allows the operations to assume there is a node (at least the
EX 4.8. Draw the UML class diagram for the iterative maze solver example from this
chapter.