23.2. Estimating Algorithm Efficiency

[Page 691 ( continued )]

Programming Exercises

Section 20.2 Lists

20.1	( Adding set operations in MyAbstractList ) Add and implement the following methods in MyAbstractList : /** Add the elements in otherList to this list. * Returns true if this list changed after the call */ public boolean addAll(MyList otherList) /** Remove all the elements in otherList from this list * Returns true if this list changed after the call */ public boolean removeAll(MyList otherList) /** Retain the elements if they are also in otherList * Returns true if this list changed after the call */ public boolean retainAll(MyList otherList) Write a test program that creates two MyArrayList s, list1 and list2 , with the initial values {"Tom", "George", "Peter", "Jean", "Jane"} and {"Tom", "George", "Michael", "Michelle", "Daniel"} , then invokes list1.addAll(list2) , list1.removeAll(list2) , and list1.retainAll(list2) , and displays the resulting new list1 .
20.2*	( Completing the implementation of MyLinkedList ) The implementations of methods removeLast() , clear() , contains(Object o) , get(int index) , indexOf(Object o) , lastIndexOf(Object o) , and set(int index, Object o) are omitted in the text. Implement these methods.
20.3*	( Creating a two-way linked list ) The MyLinkedList class used in Listing 20.5 is a one-way directional linked list that enables one-way traversal of the list. Modify the Node class to add the new field name previous to refer to the previous node in the list, as follows : public class TreeNode { Object element; TreeNode next; TreeNode previous; public TreeNode(Object o) { element = o; } } Simplify the implementation of the add(Object element, int index) and remove(int index) methods to take advantage of the bi-directional linked list.

Section 20.3 Stacks and Queues

20.4	( Using the Stack class ) Write a program that displays the first fifty prime numbers in descending order. Use a stack to store prime numbers .
20.5	( Implementing MyQueue using inheritance ) In §20.3, "Stacks and Queues," MyQueue is implemented using composition. Create a new queue class that extends MyLinkedList .

---

[Page 692]

Section 20.4 Binary Trees

20.6*	( Adding new methods in BinaryTree ) Add the following new methods in BinaryTree : /** Search element o in this binary tree */ public boolean search(Object o) /** Display the nodes in breadth-first traversal */ public void breadthFirstTraversal() /** Return the depth of this binary tree. Depth is the * number of the nodes in the longest path of the tree */ public int depth()
20.7**	( Implementing inorder traversal using a stack ) Implement the inorder method in BinaryTree using a stack instead of recursion.

Section 20.5 Heaps

20.8**	( Sorting using a heap ) Implement the following sort method using a heap: public static void sort(Object[] list)
20.9***	( Implementing heap using a binary tree ) The Heap class in the text is implemented using an array list. Implement it using a binary tree.