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

public LListRevised()
{

super ();
} // end default constructor

< Implementations of the public methods add , remove , replace , getEntry , and contains
go here. >
. . .

} // end LListRevised

The base class LinkedChainBase can be useful in other contexts as well. You can use it or
LListRevised to define an efficient implementation of the ADT sorted list, as you will see next.

An Efficient Implementation of a Sorted List

17.12

Instead of calling ADT list operations to perform operations on an ADT sorted list, our implementa-
tion will execute faster if it can be similar to the linked implementation that we wrote in the previous
chapter, beginning at Segment 16.7. The protected methods defined in the class LinkedChainBase
will enable us to manipulate the list's underlying data structure faster than if we had to rely solely on
the operations of the ADT list to do so. Thus, we want our class to extend LinkedChainBase . We
begin it by writing

public class SortedLinkedList<T extends Comparable<? super T>>
extends LinkedChainBase<T>
implements SortedListInterface<T>
As before, we will implement a sorted list of Comparable objects.

The Method add
17.13

The add operation in our new class is quite similar to the one given in Segment 16.10 for the class
SortedLinkedList . However, the details of that previous addition now are hidden within the pro-
tected methods addFirstNode and addAfterNode of LinkedChainBase . Thus, our revised method
appears as follows (changes to the add method of Segment 16.10 are highlighted):

public void add(T newEntry)
{

Node newNode = new Node(newEntry);
Node nodeBefore = getNodeBefore(newEntry);
if (nodeBefore == null ) // no need to call isEmpty
addFirstNode(newNode);
else
addAfterNode(nodeBefore, newNode);
} // end add
Preceding each of the protected methods with super is optional, since no other methods have
their names.
Question 4 in Segment 16.11 of Chapter 16 suggested the simplification for empty lists that we
made here. When a list is empty, getNodeBefore returns null . Thus, we can omit a call to isEmpty
in the if statement.