| [Page 801 (continued)] In this chapter, we have given a brief introduction to dynamic data structures and tried to illustrate how they work and why they are useful for organizing and managing large amounts of data. We also discussed 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 linked list list pop push queue reference self-referential object stack static structure traverse value
[Page 802]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 because 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 that 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) combines two elements: a collection of data, and the operations that can be performed on the data. For a 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 is 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 therefore should 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. 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 schedulersuch 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 the data stored in the left subtree and less than all the data stored in the right subtree.
|
