Java Reference
In-Depth Information
Chapter
16
Sorted Lists
Contents
Specifications for the ADT Sorted List
Using the ADT Sorted List
A Linked Implementation
The Method
add
The Efficiency of the Linked Implementation
An Implementation That Uses the ADT List
Efficiency Issues
Prerequisites
Chapter
4
The Efficiency of Algorithms
Chapter 7
Recursion
Chapter
12
Lists
Chapter
14
A List Implementation That Links Data
Objectives
After studying this chapter, you should be able to
•
Use a sorted list in a program
•
Describe the differences between the ADT list and the ADT sorted list
•
Implement the ADT sorted list by using a chain of linked nodes
•
Implement the ADT sorted list by using the operations of the ADT list
C
hapter 12 introduced you to the ADT list. The entries in a list are ordered simply
by their positions within the list. Thus, a list has a first entry, a second entry, and so
on. This ADT enables you to order entries according to any criterion you want—
alphabetical or chronological, for instance. In fact, Chapter 12 showed you an
example that used a list to organize names in alphabetical order. To do so, the client
had to determine where in the list a particular entry belonged.
