A List Implementation That Links Data - Data Structures and Abstractions with Java - page 350

List contains 4 entries, as follows:
15 is entry 1
25 is entry 2
35 is entry 3
45 is entry 4

List should not be empty; isEmpty() returns false.

Testing clear():
List should be empty; isEmpty returns true.

Question 12 Consider the method displayList , as given in Listing 12-2 of Chapter 12.
a.

Why is the method less efficient of time in the context of Listing 14-2 than it was in
Listing 12-2?

b. Revise displayList so that it is time efficient when it is used with either LList or AList .

Continuing the Implementation

To complete the class LList , we now define the methods remove , replace , getEntry , and
contains .

14.16

The method remove . To remove the first entry from our list, we execute the statement
firstNode = firstNode.getNextNode();
To remove an entry after the first one, we execute the following statements:

Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode();
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter);
nodeToRemove = null ;

Recall that the remove method returns the entry that it deletes from the list. Although the
node that contains this entry is recycled, the entry itself is not as long as the client saves the
reference to it.

VideoNote

Completing the class LList

public T remove( int givenPosition)
{

T result = null ; // return value
if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{

assert !isEmpty();
if (givenPosition == 1) // case 1: remove first entry

{

result = firstNode.getData(); // save entry to be removed

firstNode = firstNode.getNextNode();

}
else // case 2: not first entry

{

Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode();
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter);