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

16.17

Projects 1 and 2 at the end of this chapter ask you to complete the iterative and recursive implemen-
tations of the sorted list. Notice that many of the sorted list operations are the same as operations of
the ADT list and so would have implementations like those you saw in Chapter 14.

Note: Since the ADTs sorted list and list share many of the same operations, portions of their
implementations are identical.

Question 8 The linked implementation of the ADT sorted list, as given in this chapter,
does not maintain a tail reference. Why is a tail reference more significant for a linked
implementation of the ADT list than it is for a sorted list?

The Efficiency of the Linked Implementation
16.18

If you consider the analysis of the linked implementation of the ADT list given in Chapter 14, you
will see that the performance of the add method depends on the efficiency of the method getNodeAt .
The latter method locates the insertion point by traversing the chain of nodes. It is an O( n ) operation.
The add method for the sorted list does its own traversal of the list to locate where to make the addi-
tion. This traversal is also O( n ), making the addition to a sorted list an O( n ) operation.

Figure 16-5 summarizes the performance of the sorted list operations. Deriving these results is
left as an exercise. When comparing implementations, you should realize that the worst cases can
occur under different circumstances. For example, a worst-case addition to an array-based sorted
list occurs at the list's beginning, whereas for a linked implementation, it occurs at the list's end.

VideoNote

An array-based sorted list

FIGURE 16-5

The worst-case efficiencies of the operations on the ADT sorted
list for two implementations

ADT Sorted List Operation Array Linked

add(newEntry)
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)

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

An Implementation That Uses the ADT List

16.19

As we noted in Segment 16.17, the linked implementation of the ADT sorted list repeats much of
the corresponding implementation of the ADT list. Can we avoid this duplication of effort and
reuse portions of the list's implementation? The answer to this question is yes, as you will soon see.
You can certainly use the ADT list to create and maintain an alphabetical list of strings. It is
natural, then, to consider using the ADT list when implementing the ADT sorted list. Basically, you
can do this in one of two ways. Here we will use a list as a data field within the class that imple-
ments the sorted list. Figure 16-6 shows an instance of such a sorted list. Recall from Segment C.1
of Appendix C that this approach is called composition and illustrates the has-a relationship
between two classes. The next chapter considers the second approach, using inheritance to derive
the sorted list from the list.