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

17.14

The private method getNodeBefore . We still need to implement the private method getNodeBefore .
The implementation is like the one given in Segment 16.11, but it uses getFirstNode() instead of
firstNode :

private Node getNodeBefore(T anEntry)
{

Node currentNode = getFirstNode();
Node nodeBefore = null ;
while ((currentNode != null ) &&
(anEntry.compareTo(currentNode.getData()) > 0))

{

nodeBefore = currentNode;
currentNode = currentNode.getNextNode();
} // end while
return nodeBefore;
} // end getNodeBefore

17.15

Efficiency. This version of the method add executes faster than the versions given in Segments 17.1 and
16.21. Those earlier versions can use only the operations of the ADT list—that is, the public methods of
the class LList . Recall that those add methods first invoke getPosition to find where in the list the
new entry belongs, and then they invoke the list's add method. The implementation of getPosition
given in Segment 16.24 traverses the sorted list to determine the position for the new entry. Within the
O( n ) loop that performs this traversal is an invocation of the method getEntry . When getEntry has a
linked implementation, it also traverses the sorted list, and so it is O( n ). Thus, getPosition is O( n 2 ). It
follows that the add methods in Segment 17.1 and Segment 16.21 are each O( n 2 ).
Our improved add method in Segment 17.13 adds a new node in its proper location by travers-
ing the chain of nodes at most once. Even though the method must use the protected methods to
alter the chain of linked nodes, it can add the new node as soon as it finds its proper location, with-
out traversing the chain repeatedly. Thus, it is an O( n ) operation.

17.16

The rest of the class. To implement remove and getPosition , we would make similar changes to
their linked implementations. Recall that Chapter 16 left these implementations as an exercise.
Finally, we need to implement the remaining operations of the ADT list that are common to the
ADT sorted list but not inherited from LinkedChainBase . They are getEntry , contains , and
remove (by position).

Note: You can use inheritance and maintain efficiency if your base class provides protected
access to its underlying data structure.

Note: More than one implementation of an ADT is often possible. When choosing a partic-
ular implementation for a given application, you should consider all of the factors relevant to
your situation. Execution time, memory use, and extensibility are just some of the issues that
you should weigh. These same considerations should also be examined when you implement
an ADT.