16: Data Structures- Lists, Stacks, and Queues

Last updated
Save as PDF

Page ID: 15167

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Learning Objectives

Understand the concepts of a dynamic data structure and an Abstract Data Type (ADT).
Be able to create and use dynamic data structures such as linked lists and binary search trees.
Understand the stack, queue, set, and map ADTs.
Be able to use inheritance to define extensible data structures.
Know how to use the TreeSet, TreeMap, HashSet, and HashMap library classes.
Be able to use the Java generic type construct.

Introduction

A data structure is used to organize information that a computer can access and process easily and efficiently. You are already familiar with one type of data structure—arrays, which we discussed in Chapter 9. If you remember, an array is an example of a data structure in which all of the data are of the same type or class and in which individual elements are accessed by their position (index or subscript). An array is an example of a static structure, because its size is fixed for the duration of the program’s execution. (This is a different meaning of static than the Java keyword static.)

tatic.) The Vector class from Chapter 9 is another example of a data structure. Like an array, individual vector elements are accessed by their position. However, unlike arrays, a vector is an example of a dynamic structure—that is, one that can grow and shrink during a program’s execution.

These are only two of the many data structures developed by computer scientists. For more advanced problems, it is often necessary to develop specialized structures to store and manipulate information. Some of these structures—linked lists, stacks, queues, binary trees, hash tables—have become classic objects of study in computer science.

This chapter describes how to implement a linked list and how to use inheritance to extend the list to implement the stack and queue structures. Then the Java Collections Framework implementation of numerous data structures in the java.util package will be described. The data structure classes in this library make use of a new Java construct, called generic types. Finally, the binary tree data structure that is used in the Java Collections Framework will be studied briefly.

16.1: The Linked List Data Structure
As we said, a static data structure is one whose size is fixed during a program’s execution—a static structure’s memory is allocated at compile time. By contrast, a dynamic structure is one that can grow and shrink as needed. In this section, we will develop a dynamic list, which is a data structure whose elements are arranged in a linear sequence.
16.2: OBJECT-ORIENTED DESIGN: The List Abstract Data Type (ADT)
The PhoneList example from the previous section illustrates the basic concepts of the linked list. Keep in mind that there are other implementations that could have been described.
16.3: The Stack ADT
A stack is a special type of list that allows insertions and removals to be performed only to the front of the list. Therefore, it enforces last-in–firstout (LIFO) behavior on the list. Think of a stack of dishes at the salad bar. When you put a dish on the stack, it goes onto the top of the stack. When you remove a dish from the stack, it comes from the top of the stack
16.4: The Queue ADT
A queue is a special type of list that limits insertions to the end of the list and removals to the front of the list. Therefore, it enforces first-in–first-out (FIFO) behavior on the list. Think of the waiting line at the salad bar. You enter the line at the rear and you leave the line at the front
16.5: From the Java Library: The Java Collections Framework and Generic Types
Declaring classes that use the generic type construct introduced in Java 5.0 generic types involves using new syntax to refer to the class name. Such classes and interfaces, including those in the collections framework, use angle brackets containing one or more variables (separated by commas) to refer to unspecified type names.
16.6: Using the Set and Map Interfaces
The Set and Map interfaces are similar to the List interface in that there are multiple classes in the collections framework that implement them.
16.7: The Binary Search Tree Data Structure
To gain some appreciation of what binary search trees are and why they are useful in implementing the Set and Map interfaces, let’s make a few comments about implementing very simple versions of these structures.
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.