Inheritance and Lists - Data Structures and Abstractions with Java - page 442

8.

Repeat Exercise 7, but consider the class SortedLinkedList , as described in Segment 17.12, instead of Linked -
ChainBase .

9.

Suppose that the class LinkedChainBase , as given in Segment 17.10, implements the interface java.util.List -
Iterator , as described in Segment 15.32. If LinkedChainBase is a base class of SortedLinkedList , which of the
iterator methods are appropriate for a sorted list?

P ROJECTS

1.

Complete the implementation of the class SortedLinkedList that Segment 17.12 began.

2.

Derive the class SortedLinkedList from the class LListRevised , as described in Segment 17.11. What is the
disadvantage of this approach?

3.

Exercise 4 in Chapter 16 asked you to design the ADT activity list. Show how you would implement such a class
by using inheritance, with LListRevised as the base class.

4.

Project 8 in Chapter 16 asked you to implement the method mode . Show how you would implement this method
for the class SortedLinkedList , as described in Segment 17.12.

5.

Using inheritance, derive the class LinkedListWithIterator , as described in Chapter 15 in Segment 15.19, from
the class LListRevised .

6.

Define a class of bags that implements the interface BagInterface , as given in Listing 1-1 of Chapter 1, and is a
subclass of LinkedChainBase , as given in Listing 17-2.

A NSWERS TO S ELF -T EST Q UESTIONS

1.

The list's method contains searches the entire list when the desired entry is not present. By calling getPosition ,
contains can take advantage of the sorted order of the entries. The answer to Question 13 of Chapter 16 gives
such a method. By adding this method to SortedList , you can override LList 's contains .

2.

The client will be unaware of what has happened and will not know where in the sorted list the addition was made.

3.

Advantages: The implementation is easy to write. You inherit methods such as isEmpty that you do not have to
implement.
Disadvantages: The implementation is not efficient, especially when the implementation of the underlying list is
linked. Using inheritance in this way is as inefficient as using composition. You inherit methods (add and replace
by position) that you do not want. Moreover, since inheritance implies an is a relationship between the sorted list
and the list, type compatibility dictates that the sorted list be able to behave like a list. This clearly is not the case,
since you cannot insert or replace entries at any given position. Thus, a sorted list is not really a list.

4.

a. public void addToBeginning(T newEntry)
{

addFirstNode( new Node(newEntry));
} // end addToBeginning

b. public void addAfterMidpoint(T newEntry)
{

Node nodeBefore = getNodeAt(getLength() / 2);
addNodeAfter(nodeBefore, new Node(newEntry));
} // end addAfterMidpoint