Java, Java, Java

 

To gain some appreciation of what binary search trees are and why they are useful in implementing the Set and Map interfaces, let’s make a few comments about implementing very simple versions of these structures.

Like a linked list, a binary tree is a data structure consisting of a col- lection of nodes that are linked together by references from one node to another. However, unlike a linked list, each node in a binary tree contains references to two other other nodes, (left and right), corresponding to the left- and right-subtrees growing out of a particular node. A subtree is a tree that is part of larger tree. This creates a tree-like structure, as shown in Figure 16.36. Note that some of the references to other nodes might be null. The trunk of the tree corresponds to the node labeled root. In computer science, trees are almost always drawn upside down. Thus the trunk of the tree, root, is at the top of the figure.

If we assume that the objects contained in a tree are from a class that

implements the Comparable interface, then a binary search tree is a bi- nary tree in which the objects are ordered so that the object at a particular node is greater than the objects stored in its left subtree and less than the objects stored in its right subtree.

Figure 16.36 shows a binary search tree with the phone list data that we have used throughout the chapter. Objects are compared by comparing the names alphabetically. From the figure it is easy to see that searching for a object should start at the root of the tree. At each node, examining the name at the node will tell you whether you have found the object there. Otherwise, by checking the name at the node, you can decide which sub- tree the data could be in, and you can traverse either left or right through each level of the tree. One can deduce that if the tree is balanced—that is, if at most nodes the size of the left subtree is about the same size as the right subtree—searching the tree much faster than searching a linked list.

 

Figure 16.36: A binary search tree of PhoneTreeNodes.

 

 

 

 

 

 

 

This is one of the main advantages of using a binary search tree over a linked list.

The TreeSet and TreeMap classes implement sophisticated algo- rithms for inserting and removing data from a tree, which guarantees that the tree remains relatively balanced. The details of these algorithms are beyond the scope of this book, but would be a subject of study in a standard Data Structures and Algorithms course.

We will conclude this subsection by giving a brief outline of an imple- mentation of a simple binary search tree that stores our phone list data. Like our LinkedList example, you need to define a node class and a tree class. The node class with unimplemented methods, would look like:

,,

 

 

 

 

 

 

 

 

 

 

J

 

The tree structure itself contains a reference to a node:

,,

 

 

 

 

 

J

We will implement only the two contains() methods. The PhoneTree version is very simple:

,,

 

 

 

J

The implementation of the contains() method of PhoneTreeNode is only slightly more involved.

,,

 

 

 

 

 

 

 

 

J

 

 

 

CHAPTER SUMMARYIn this chapter, we have given you a brief introduction to the concept of

a dynamic data structure and tried to illustrate how they work and why they are useful for organizing and managing large amounts of data. We also introduced you to an important new language feature introduced in Java 5.0, the concept of generic types. Obviously, we have only scratched the surface of the important topic of data structures and the algorithms used to manage them. For a broader and deeper treatment of this subject, you will have to take a Data Structures and Algorithms course, which is a fundamental course in most computer science curricula.

Technical Terms

 

Abstract Data Type (ADT)

binary search tree data structure dequeue

dynamic structure enqueue

first-in–first-out (FIFO)

generic type

Java collections framework

key

last-in–first-out (LIFO)

link list

linked list pop

push

queue reference

self-referential object stack

static structure traverse

value vector

 

Summary of Important Points

A data structure is used to organize data and make them more efficient to process. An array is an example of a static structure, since its size does not change during a program’s execution. A vector is an example of a dynamic structure, one whose size can grow and shrink during a program’s execution.

A linked list is a linear structure in which the individual nodes of the list are joined together by references. A reference is a variable that refers to an object. Each node in the list has a link variable that refers to another node. An object that can refer to the same kind of object is said to be self-referential.

The Node class is an example of a self-referential class. It contains a link variable that refers to a Node. By assigning references to the link variable, Nodes can be chained together into a linked list. In addition to their link variables, Nodes contain data variables, which should be accessible through public methods.

Depending on the use of a linked list, nodes can be inserted at various locations in the list: at the head, the end, or in the middle of the list.

Traversal algorithms must be used to access the elements of a singly linked list. To traverse a list you start at the first node and follow the links of the chain until you reach the desired node.

Depending on the application, nodes can be removed from the front, rear, or middle of a linked list. Except for the front node, traversal algorithms are used to locate the desired node.

In developing list algorithms, it is important to test them thoroughly. Ideally, you should test every possible combination of insertions and

 

removals that the list can support. Practically, you should test every independent case of insertions and removals that the list supports.

An Abstract Data Type (ADT) is a concept that combines two elements: A collection of data, and the operations that can be performed on the data. For the list ADT, the data are the values (Objects or ints) contained in the nodes that make up the list, and the operations are insertion, removal, and tests of whether the list is empty.

In designing an ADT, it’s important to provide a public interface that can be used to access the ADT’s data. The ADT’s implementation de- tails should not matter to the user and should, therefore, be hidden. A Java class definition, with its public and private aspects, is perfectly suited to implement an ADT.

A stack is a list that allows insertions and removals only at the front of the list. A stack insertion is called a push and a removal is called a pop. The first element in a stack is usually called the top of the stack. The Stack ADT can easily be defined as a subclass of List. Stacks are used for managing the method call and return in most programming languages.

A queue is a list that only allows insertions at the rear and removals from the front of a list. A queue insertion is called enqueue, and a re- moval is called dequeue. The Queue ADT can easily be defined as a subclass of List. Queues are used for managing the various lists used by the CPU scheduler—such as the ready, waiting, and blocked queues. A binary search tree is a binary tree in which the ordered data stored at any node is greater than all data stored in the left subtree and is less than all data stored in the right subtree.

 

 

 

 

 

 

 

SOLUTION 16.1

,,

SOLUTIONS TO

SELF-STUDY EXERCISES

 

 

J

 

 

SOLUTION 16.2

,,

 

J

 

 

SOLUTION 16.3

,,

 

 

J

 

SOLUTION 16.4 The following condition is too general. It will cause the loop to exit as soon as a nonnull node is encountered, whether or not the node matches the one being sought.

,,

 

J

 

 

 

 

 

 

 

SOLUTION 16.5 The PhoneList program will generate the following output, which has been edited slightly to improve its readability:

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

 

SOLUTION 16.6 Executing the following method calls will test whether it is possible to insert items into a list after items have been removed:

,,

 

 

 

 

 

 

 

 

 

J

 

 

 

 

 

 

 

 

 

SOLUTION 16.7 The List ADT program will produce the following output:

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

 

SOLUTION 16.8 Executing the following method calls will test whether it is possible to insert items into a List after items have been removed:

,,

 

 

 

 

 

 

 

 

 

 

 

 

J

 

 

 

 

SOLUTION 16.9 The peek() method should just return the first node without deleting it:

,,

 

 

J

 

 

 

 

SOLUTION 16.10 The peekLast() method can be modeled after the List.re- moveLast() method:

,,

 

 

 

 

 

 

 

 

J

 

SOLUTION 16.11 The following class tests the java.util.Stack<E> class:

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

J

 

 

 

EXERCISE 16.1 Explain the difference between each of the following pairs of terms:

EXERCISES

 

Stack and queue.

Static structure and dynamic structure.

Data structure and Abstract Data Type.

EXERCISE 16.2 Fill in the blanks.

Push and pop.

Enqueue and dequeue.

Linked list and node.Note: For programming exercises, first draw a UML class diagram describing all classes and their

 

An Abstract Data Type consists of two main parts:and.

An object that contains a variable that refers to an object of the same class is a

.

One application for ais to manage the method call and returns in a computer program.

One application for ais to balance the parentheses in an arithmetic expression.

Aoperation is one that starts at the beginning of a list and processes each element.

A vector is an example of adata structure.

An array is an example of adata structure.

By default, the initial value of a reference variable is.

EXERCISE 16.3 Add a removeAt() method to the List class to return the object at a certain index location in the list. This method should take an int parameter, specifying the object’s position in the list, and it should return an Object.

EXERCISE 16.4 Add an insertAt() method to the List class that will insert an object at a certain position in the list. This method should take two parameters, the Object to be inserted, and an int to designate where to insert it. It should return a boolean to indicate whether the insertion was successful.

inheritance relationships and/or associations.

 

EXERCISE 16.5 Add a removeAll() method to the List class. This void

method should remove all the members of the list.

 

EXERCISE 16.6 Write an int method named size() that returns the number of elements in a List.

EXERCISE 16.7 Write an boolean method named contains(Object o)

that returns true if its Object parameter is contained in the list.

EXERCISE 16.8 The head of a list is the first element in the list. The tail of a list consists of all the elements except the head. Write a method named tail() that returns a reference to the tail of the list. Its return value should be Node.

EXERCISE 16.9 Write a program that uses the List ADT to store a list of 100 random floating-point numbers. Write methods to calculate the average of the numbers.

EXERCISE 16.10 Write a program that uses the List ADT to store a list of Student records, using a variation of the Student class defined in Chapter 11. Write a method to calculate the mean grade point average for all students in the list.

EXERCISE 16.11 Write a program that creates a copy of a List. It is necessary to copy each node of the list. This will require that you create new nodes that are copies of the nodes in the original list. To simplify this task, define a copy constructor for your node class and then use that to make copies of each node of the list.

EXERCISE 16.12 Write a program that uses a Stack ADT to determine if a string is a palindrome—spelled the same way backward and forward.

EXERCISE 16.13 Design and write a program that uses a Stack to determine whether a parenthesized expression is well-formed. Such an expression is well formed only if there is a closing parenthesis for each opening parenthesis.

EXERCISE 16.14 Design and write a program that uses Stacks to determine whether an expression involving both parentheses and square brackets is well formed.

EXERCISE 16.15 Write a program that links two lists together, appending the second list to the end of the first list.

EXERCISE 16.16 Design a Stack class that uses a Vector instead of a linked list to store its elements. This is the way Java’s Stack class is defined.

EXERCISE 16.17 Design a Queue class that uses a Vector instead of a linked list to store its elements.

 

EXERCISE 16.18 Write a program that uses the List<E> and LinkedList<E> classes to store a list of Student records, using a variation of the Student class defined in Chapter 11. Write a method to calculate the mean grade point average for all students in the list.

EXERCISE 16.19 Write an implementation of the insert() method of the

PhoneTree class described at the end of this chapter.

EXERCISE 16.20 Write an implementation of the insert() method of the

PhoneTreeNode class described at the end of this chapter.

 

EXERCISE 16.21 Challenge: Design a List class, similar in functionality to the one we designed in this chapter, that uses an array to store the list’s elements. Set it up so that the middle of the array is where the first element is placed. That way you can still insert at both the front and rear of the list. One limitation of this approach is that, unlike a linked list, an array has a fixed size. Allow the user to set the initial size of the array in a constructor, but if the array becomes full, don’t allow any further insertions.

EXERCISE 16.22 Challenge: Add a method to the program in the previous exercise that lets the user increase the size of the array used to store the list.

EXERCISE 16.23 Challenge: Recursion is a useful technique for list processing. Write recursive versions of the print() method and the lookup-by-name method for the PhoneList. (Hint: The base case in processing a list is the empty list. The recursive case should handle the head of the list and then recurse on the tail of the list. The tail of the list is everything but the first element.)

EXERCISE 16.24 Challenge: Design an OrderedList class. An ordered list is one that keeps its elements in order. For example, if it’s an ordered list of integers, then the first integer is less than or equal to the second, the second is less than or equal to the third, and so on. If it’s an ordered list of employees, then perhaps the employees are stored in order according to their social security numbers. The OrderedList class should contain an insert(Object o) method that inserts its object in the proper order. One major challenge in this project is designing your class so that it will work for any kind of object. (Hint: Define an Orderable interface that defines an abstract precedes() method. Then define a subclass of Node that implements Orderable. This will let you compare any two Nodes to see which one comes before the other.)

 

 

 

 

 

 

 

 

 

 

 

Appendix A