Sorted Lists - Data Structures and Abstractions with Java - page 424

16.26

The efficiency of getPosition . As we examine getPosition , as given in Segment 16.24, we note
that the list method getLength is an O(1) operation. Therefore, we need not be concerned with it.
On the other hand, a loop examines the entries in the list one at a time by invoking getEntry until
the desired entry is located. Thus, the efficiency of getPosition depends in part on the efficiency
of getEntry . However, the efficiency of getEntry depends upon which implementation of the
ADT list you use. We will examine two list implementations that lead to rather different efficien-
cies for getPosition .
Chapter 14 discussed the efficiencies of the ADT list operations. Figure 16-8 recalls the worst-
case performance of the list operations that we need to complete our analysis of the sorted list. If
you use an array to represent the entries in a list, getEntry is always an O(1) operation. The loop in
getPosition is therefore O( n ) in the worst case, and so getPosition is O( n ) when the list has an
array-based implementation.
If you use a chain of linked nodes to contain the entries in a list, the method getEntry is O( n ).
Since getPosition 's loop invokes getEntry , we see that getPosition is O( n 2 ) in the worst case.
Each time getEntry retrieves the next entry in the list, it starts its search at the beginning of the
chain. This fact is the cause of getPosition 's inefficiency.

FIGURE 16-8

The worst-case efficiencies of selected ADT list operations for
array-based and linked implementations

ADT List Operation Array Linked

getEntry(givenPosition)
add(newPosition, newEntry)
remove(givenPosition)
contains(anEntry)
toArray()
clear(), getLength(), isEmpty()

O(1)
O( n )
O( n )
O( n )
O( n )
O(1)

O( n )
O( n )
O( n )
O( n )
O( n )
O(1)

16.27

The efficiency of add . The implementation of the sorted list method add given in Segment 16.21
contains the following statements:

int newPosition = Math.abs(getPosition(newEntry));
list.add(newPosition, newEntry);
For an array-based implementation of the ADT list, both getPosition and the list operation add
are O( n ) operations. Thus, the sorted list operation add is O( n ) in the worst case. For a linked
implementation of the list, getPosition 's worst-case behavior is O( n 2 ) and dominates the list
operation add , which is only O( n ). Thus, the sorted list operation add is O( n 2 ) in the worst case.

16.28

Figure 16-9 summarizes the efficiencies of the sorted list operations for array-based and linked
implementations of the ADT list. Confirmation of these results is left as an exercise. As you can
see, the implementation of the sorted list given in this section is easy to write but is not very effi-
cient if the underlying list uses a chain of linked nodes. The next chapter will show you how you
can reuse the ADT list in the implementation of the sorted list without sacrificing efficiency.

Question 15 Give an advantage and a disadvantage of using composition in the imple-
mentation of the class SortedList .