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

The following method treats the previous two cases in its implementation of the remove
operation:
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();
if (numberOfEntries == 1)
lastNode = null ; // solitary entry was removed

}
else // case 2: not first entry

{

Node nodeBefore = getNodeAt(givenPosition - 1);
Node nodeToRemove = nodeBefore.getNextNode();
Node nodeAfter = nodeToRemove.getNextNode();
nodeBefore.setNextNode(nodeAfter);
result = nodeToRemove.getData(); // save entry to be removed

if (givenPosition == numberOfEntries)
lastNode = nodeBefore; // last node was removed

} // end if
numberOfEntries--;
} // end if
return result;

// return removed entry, or
// null if operation fails

} // end remove

Note: Adding to the end of a chain of linked nodes requires less work when you maintain a
tail reference because you avoid a traversal of the chain. Removing the last node from a chain
requires a traversal to locate the next-to-last node whether or not you have a tail reference.

Question 16 In light of the tail reference, what changes should you make to the assertions
in the method isEmpty , as given in Segment 14.12?

The Efficiency of Using a Chain to Implement the ADT List

Let's consider the time complexity of some of the methods in our classes LList and LList2 . Sev-
eral of these methods call the private method getNodeAt , as given in Segment 14.7. The loop in
getNodeAt cycles i times in its search for the i th node in the chain. Thus, getNodeAt is O( n ). We
will use this fact in our analysis of the public methods.

14.25

Adding to the end of the list. Because the chain in the class LList does not have a tail reference,
LList 's add method, as described in Segment 14.9, must traverse the entire chain of linked nodes to
locate the last one before it can add an entry at the end of the list. The method calls getNodeAt to
locate this node. Since getNodeAt is O( n ), this add method is also O( n ).
The class LList2 , on the other hand, does maintain a tail reference for its chain of linked
nodes. Thus, its add method, as given in Segment 14.22, does not call getNodeAt , and so is O(1).