16.8: Chapter Summary

In 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)	Java collections framework	queue
binary search tree	key	reference
data structure	last-in–first-out (LIFO)	self-referential object
dequeue	link	stack
dynamic structure	list	static structure
enqueue	linked list	traverse
first-in–first-out (FIFO)	pop	value
generic type	push	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 details 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 removal 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.

SOLUTIONS TO SELF-STUDY EXERCISES

SOLUTION 16.1

Node node = new Node (new String (”Hello”));

SOLUTION 16.2

Node node = new Node (new Student (”William”));

SOLUTION 16.3

PhoneListNode newNode =

new PhoneListNode (”BillC” , ”111−202−3331”);

nodeptr.setNext (newNode);

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.

((current.getNext()!=null) ||

(!current.getName().equals(name)))

SOLUTION 16.5

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

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:

//Create and insert some nodes

PhoneList list = new PhoneList();

list.insert (new PhoneListNode (”Roger M” , ”997−0020”));

list.insert (new PhoneListNode (”Roger W” , ”997−0086”));

System.out.println(list.remove (”Roger M”));

list.insert(new PhoneListNode ( ”Rich P” , ”997−0010”));

System.out.println (list.remove (”Roger W”));

list.insert (new PhoneListNode (” Jane M” , ”997−2101”));

list.insert (new PhoneListNode (” Stacy K” , ”997−2517”));

System.out.println (list.remove (” Jane M”));

System.out.println (list.remove (”Stacy K”));

list.print();

// List should be empty

SOLUTION 16.7

The List ADT program will produce the following output:

Generic List

_____________________

Hello, World!

8647

Roger M 997−0020

Jane M 997−2101

Stacy K 997−2517

Removed Stacy K 997−2517

Generic List:

Hello, World!

8647

Roger M 997−0020

Jane M 997−2101

Removed Jane M 997−2101

Generic List:

Hello, World!

8647

Roger M 997−0020

Removed Hello, World!

Generic List:

8647

Roger M 997−0020    

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:

//Create and insert some nodes

Listlist = new List();

list.insertAt Front (new PhoneRecord ( ”Roger M” , ”997−0020”));

list.insertAtFront (new PhoneRecord (”Roger W” , ”997−0086”));

System.out.println (”Current List Elements”);

list.print();

Object o = list.removeLast(); //Remove last element

list.insertAtFront(o); //Insert at the front of the list

System.out.println(”Current List Elements”);

list.print();

o = list.removeFirst();

System.out.println(”Removed” + o.toString());

o = list.removeFirst();

System.out.println(”Removed” + o.toString());

list.insertAtRear(o);

System.out.println(”Current List Elements”);

list.print(); //List should have one element

SOLUTION 16.9

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

public Object peek ( ) {

return head;

}

SOLUTION 16.10

The peekLast() method can be modeled after the List.removeLast() method:

public Object peekLast(){

if (isEmpty())

return null;

else{

Node current = head ; // Start at head of list

while (current.getNext()!=null) //Find end of list

current = current.getNext();

return current;

// Return last node

}

} //peek Last()

SOLUTION 16.11

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

import java.util.∗;

public class StackTest{

public static void main (String argv []){

Stack<Character> stack = new Stack<Character>();

String string = ” Hello this is a test string”;

 

System.out.println (”String:” + string);

for (int k = 0 ; k < string.length(); k++)

stack.push (new Character (string.charAt(k)));

 

Character ch = null;

String reversed = ”” ;

while (!stack.empty()){

ch = stack.pop();

reversed = reversed + ch.charValue();

}

System.out.println (”Reversed String:” + reversed);

} //main()

} //StackTest class

EXERCISES

Note

For programming exercises, first draw a UML class diagram describing all classes and their inheritance relationships and/or associations.

Exercise 16.1

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

1. Stack and queue.
2. Static structure and dynamic structure.
3. Data structure and Abstract Data Type.
4. Push and pop.
5. Enqueue and dequeue.
6. Linked list and node.

Exercise 16.2

Fill in the blanks.

1. An Abstract Data Type consists of two main parts: _____________ and _____________.
2. An object that contains a variable that refers to an object of the same class is a _____________.
3. One application for a _____________ is to manage the method call and returns in a computer program.
4. One application for a _____________ is to balance the parentheses in an arithmetic expression.
5. A _____________ operation is one that starts at the beginning of a list and processes each element.
6. A vector is an example of a _____________ data structure.
7. An array is an example of a _____________ data structure.
8. 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.

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.)