Skip to main content
Logo image

Java, Java, Java: Object-Oriented Problem Solving, 2022E

Ralph Morelli, Ralph Walde, Beryl Hoffman

Section 16.10 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.

Subsection 16.10.1 Technical Terms

Abstract Data Type (ADT) linked list
binary search tree list
data structure pop
dequeue push
dynamic structure queue
enqueue reference
first-in–first-out (FIFO) self-referential object
generic type stack
Java collections framework static structure
key traverse
last-in–first-out (LIFO) value
link

Subsection 16.10.2 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. An ArrayList 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, Node s can be chained together into a linked list. In addition to their link variables, Node s 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 (Object s or int s) 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 StackADT 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 QueueADT 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 16.10.3 Solutions to Self-Study Exercises

16.2 The Linked List Data Structure
16.2.1 Using References to Link Objects

Self-Study Exercises
16.2.1.1. New String Node.
Solution.
Either of these statements would work: 
Node node = new Node(new String("Hello"));
Node node = new Node("Hello");
16.2.1.2. New Integer Node.
Solution.
The value 100 must be converted into an Object.
Node node = new Node(new Integer(100));

16.2.2 Example: The Dynamic Phone List

Self-Study Exercise
16.2.2.1. New PhoneListNode.
Solution.
PhoneListNode newNode = new PhoneListNode("Bill C", "111-202-3331");
nodeptr.setNext(newNode);

16.2.6 Looking up a Node in a List

Self-Study Exercise
16.2.6.1. Loop Exit Condition.
Solution.
The exit 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.

16.2.8 Testing the List

Self-Study Exercises
16.2.8.2. PhoneList Test, Part 2.
Solution.
Executing something like the following method calls will test whether it is possible to insert items into a list after all 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"));
list.print();
System.out.println(list.remove("Roger M") );
System.out.println(list.remove("Roger W") );
list.print();
       // List should be empty
list.insert(new PhoneListNode("Rich P", "997-0010"));
list.insert(new PhoneListNode("Jane M", "997-2101"));
list.insert(new PhoneListNode("Stacy K", "997-2517"));
list.print();
System.out.println(list.remove("Jane M"));
System.out.println(list.remove("Stacy K"));
System.out.println(list.remove("Rich P"));
list.print();
       // List should be empty

16.3 OBJECT-ORIENTED DESIGN: The List Abstract Data Type (ADT)
16.3.4 Testing the List ADT

Self-Study Exercises
16.3.4.2. PhoneRecord Test, Part 2.
Solution.
Executing something like the following method calls will test whether it is possible to insert items into a List after all items have been removed:
// Create and insert some nodes
List list = new List();
list.insertAtFront(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());
System.out.println("Current List Elements");
list.print();                  // List should be empty.
list.insertAtRear(o);
System.out.println("Current List Elements");
list.print();       // List should have one element

16.4 The Stack ADT
16.4.1 The StackClass

Self-Study Exercise
16.4.1.1. Stack Reverse String.
Solution.
public static void main(String argv[]) {
    Stack stack = new Stack();
    String string = "Hello this is a test string";
    System.out.println("String: " + string);
    for (int k = 0; k < string.length(); k++)
        stack.push(Character.valueOf(string.charAt(k)));
    Object o = null;
    String reversed = "";
    while (!stack.isEmpty()) {
        o = stack.pop();
        reversed = reversed + o.toString();
    }
    System.out.println("Reversed String: " + reversed);
} // main()
16.4.1.2. Stack Peek.
Solution.
The peek() method should just return the first node without deleting it: 
public Object peek() {
     return head;
}

16.5 The Queue ADT
16.5.1 The Queue Class

Self-Study Exercise
16.5.1.1. Queue Test.
Solution.
public static void main(String argv[]) {
    Queue queue = new Queue();
    String string = "Hello this is a test string";
    System.out.println("String: " + string);
    for (int k = 0; k < string.length(); k++)
        queue.enqueue(Character.valueOf(string.charAt(k)));
    System.out.println("The current queue:");
    queue.print();
    Object o = null;
    System.out.println("Dequeuing:");
    while (!queue.isEmpty()) {
        o = queue.dequeue();
        System.out.print(o.toString());
    }
} // main()
16.5.1.2. Queue Peek.
Solution.
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
    }
} // peekLast()

16.7 From the Java Library: The Java Collections Framework and Generic Types
16.7.2 The java.util.Stack<E> class

Self-Study Exercise
16.7.2.1.
Solution.
The following class tests the java.util.Stack<E> class: 
import java.util.*;
public class StackTest{
public static void main( String args[] ) {
   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(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

16.8 Using the Set and Map Interfaces
16.8.3 Using the Map<K,V> Interface

Self-Study Exercise
16.8.3.1.
Solution.
  import java.util.*;
  
  public class TranslateMap {  
  
    public static void testMap() {
      Map<String, String> theMap =
         new TreeMap<String,String>();
      // new HashMap<K,V>(); could also be used
      theMap.put("cat", "gato");
      theMap.put("dog", "perro");

      System.out.print("cat in Spanish: ");
      System.out.println(theMap.get("cat"));
      System.out.print("dog in Spanish: ");
      System.out.println(theMap.get("dog"));
    } // testMap
    
    public static void main(String args[]) {
      testMap();
    } // main()
  }

16.9 The Binary Search Tree Data Structure

Self-Study Exercise
16.9.1.
Solution.
In class PhoneTree:
public void insert(String nam, String pho){ 
  if (root == null) 
        root = new PhoneTreeNode(nam, pho);
   else 
        root.insert(nam, pho);
 }
In class PhoneTreeNode:
  public void insert(String nam, String pho){    
    if (name.compareTo(nam) <= 0) { // name <= nam
        if (right == null) 
            right = new PhoneTreeNode(nam, pho);
        else 
            right.insert(nam, pho);
    } else { // name > nam
        if (left == null) 
            left = new PhoneTreeNode(nam, pho);
        else 
            left.insert(nam, pho);
    } // else
} // insert
You have attempted of activities on this page.
PrevTopNext