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|
|first-in–first-out (FIFO)||self-referential object|
|Java collections framework||static structure|
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
ArrayListis 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.
Nodeclass 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 (
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
privateaspects, 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.