Java Reference
In-Depth Information
4
Lists, Stacks, and Queues
If your program needs to store a few things — numbers, payroll records, or job de-
scriptions for example — the simplest and most effective approach might be to put
them in a list. Only when you have to organize and search through a large number
of things do more sophisticated data structures usually become necessary. (We will
study how to organize and search through medium amounts of data in Chapters 5, 7,
and 9, and discuss how to deal with large amounts of data in Chapters 8-10.) Many
applications don't require any form of search, and they do not require that any or-
dering be placed on the objects being stored. Some applications require processing
in a strict chronological order, processing objects in the order that they arrived, or
perhaps processing objects in the reverse of the order that they arrived. For all these
situations, a simple list structure is appropriate.
This chapter describes representations for lists in general, as well as two impor-
tant list-like structures called the stack and the queue. Along with presenting these
fundamental data structures, the other goals of the chapter are to: (1) Give examples
of separating a logical representation in the form of an ADT from a physical im-
plementation for a data structure. (2) Illustrate the use of asymptotic analysis in the
context of some simple operations that you might already be familiar with. In this
way you can begin to see how asymptotic analysis works, without the complica-
tions that arise when analyzing more sophisticated algorithms and data structures.
(3) Introduce the concept and use of dictionaries.
We begin by defining an ADT for lists in Section 4.1. Two implementations for
the list ADT — the array-based list and the linked list — are covered in detail and
their relative merits discussed. Sections 4.2 and 4.3 cover stacks and queues, re-
spectively. Sample implementations for each of these data structures are presented.
Section 4.4 presents the Dictionary ADT for storing and retrieving data, which sets
a context for implementing search structures such as the Binary Search Tree of
Section 5.4.
93
