Java Software Structures, 4th Edition Exercise Solutions, Ch. 6
Chapter 6 Exercise Solutions
EX 6.1. Hand trace an ordered list X through the following operations.
An ordered list keeps the items in order no matter when they are added. So the
evolution of the list is as follows:
Operation
List
X.add(new Integer(4));
4
X.add(new Integer(7));
4 7
Object Y = X.first();
4 7 (Y takes on 4, list not change)
X.add(new Integer(3));
3 4 7
X.add(new Integer(2));
2 3 4 7
X.add(new Integer(5));
2 3 4 5 7
Object Y = X.removeLast();
2 3 4 5
Object Y = X.remove(new Integer(7));
2 3 4 5 (Y takes on null)
X.add(new Integer(9));
2 3 4 5 9
EX 6.2. Given the resulting list X from Exercise 6.1, what would be the result of each of the
following?
X.last()
returns 9
X.first();
returns 2
X.first();
returns 3
z = X.contains(new Integer(3));
z takes on true
EX 6.3. What would be the time complexity of the size operation for each of the
implementations if there were not a count variable?
Without keeping track of the number of elements in the list explicitly, it would
EX 6.4. In the linked implementation, under what circumstances could the head and tail
references be equal?
EX 6.5. In the array implementation, under what circumstances could the rear reference
equal 0?
EX 6.6. Hand trace an unordered list through the following operations.
EX 6.7. If there were not a count variable in the array implementation, who could you
detrmine whether or not the list was full?