Skip to main content

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.2 Example: The Dynamic Phone List

Self-Study Exercise

16.2.6 Looking up a Node in a List

Self-Study Exercise

16.2.8 Testing the List

Self-Study Exercises

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.

16.4 The Stack ADT
16.4.1 The StackClass

Self-Study Exercise

16.5 The Queue ADT
16.5.1 The Queue Class

Self-Study Exercise

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.8 Using the Set and Map Interfaces
16.8.3 Using the Map<K,V> Interface

Self-Study Exercise

16.9 The Binary Search Tree Data Structure

Self-Study Exercise
You have attempted of activities on this page.