Java Reference
In-Depth Information
FIGURE 16-9
The worst-case efficiencies of the ADT sorted list operations
when implemented using an instance of the ADT list
ADT Sorted List Operation
List Implementation
Array
Linked
O(
n
2
)
O(
n
2
)
O(
n
2
)
O(
n
)
O(
n
)
O(
n
)
O(
n
)
O(1)
add(new Entry)
remove(anEntry)
getPosition(anEntry)
getEntry(givenPosition)
contains(anEntry)
remove(givenPosition)
toArray()
clear(), getLength(), isEmpty()
O(
n
)
O(
n
)
O(
n
)
O(1)
O(
n
)
O(
n
)
O(
n
)
O(1)
Note:
Using composition to implement the ADT sorted list
When you use an instance of an ADT list to represent the entries in the ADT sorted list, you
must use the list's operations to access the sorted list's entries, instead of accessing them
directly. Such an implementation of the sorted list is easy to write but is inefficient when the
underlying list uses a chain of linked nodes to store its entries.
C
HAPTER
S
UMMARY
•
The ADT sorted list maintains its entries in sorted order. It, not the client, determines where to place an entry.
•
The ADT sorted list can add, remove, or locate an entry, given the entry as an argument.
•
The sorted list has several operations that are the same as the corresponding operations of the ADT list.
However, a sorted list will not let you add or replace an entry by position.
•
A chain of linked nodes provides a reasonably efficient implementation of the sorted list.
•
An implementation of the sorted list that uses an ADT list as a data field is easy to write. However, depend-
ing upon how the ADT list is implemented, its efficiency can suffer.
E
XERCISES
1.
Suppose that
nameList
is a sorted list of names. Using the operations of the ADT list and the ADT sorted list,
create a list of these names without changing their order.
2.
As specified in this chapter, the sorted list can contain duplicate entries. Specify a sorted list of unique items. For
example,
add
could return true if it added an entry to the list but return false if the entry is in the list already.
3.
The
mode
of a list of values is the value having the greatest frequency.
a.
Write an algorithm to find the mode of a sorted list using only methods of the ADT sorted list.
b.
What is the Big Oh of the algorithm if the sorted list has an array-based implementation?
c.
What is the Big Oh of the algorithm if the sorted list has a linked implementation?
