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

if ((givenPosition >= 1) && (givenPosition <= numberOfEntries))
{

assert !isEmpty();
result = getNodeAt(givenPosition).getData();
} // end if
return result;
} // end getEntry

The method getNodeAt returns a reference to the desired node, so
getNodeAt(givenPosition).getData()
is the data portion of that node.
Although our implementations of getEntry and replace are easy to write, each does more
work than if we had used an array to represent the list. Here, getNodeAt starts at the first node in the
chain and moves from node to node until it reaches the desired one. In Segment 13.12, you saw that
replace and getEntry can reference the desired array entry directly, without involving any other
entry in the array.

14.19

The method contains . The method contains for a list could have the same definition as the one
given in Segment 3.17 of Chapter 3 for a bag. However, the inner class Node now has set and get
methods, so contains can appear as follows:

public boolean contains(T anEntry)
{

boolean found = false ;
Node currentNode = firstNode;
while (!found && (currentNode != null ))
{

if (anEntry.equals(currentNode.getData()))
found = true ;
else
currentNode = currentNode.getNextNode();
} // end while
return found;
} // end contains
Because the ADT bag has a remove method that removes a given entry, it must do the same
search as contains . For that reason, we revised the definition of contains in Chapter 3 so that the
search is performed by a private method that both contains and remove can call. Our version of the
ADT list, however, removes entries by position, not by the value of the entry. Thus, the search that
contains does is performed only by contains .

Note: Test the class LList
The class LList is now complete and should be thoroughly tested before we continue. We
leave this test to you as an exercise. You will be able to use your program later when you test
the improved version of LList that we are about to write.

A Refined Implementation

Currently, the chain of linked nodes that contains a list's entries has only a head reference. When
we began writing the class LList , we noted that the first add method, which adds a new entry at the
end of the chain, must invoke the private method getNodeAt to locate the chain's last node. To do