Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 5
The method dataStructures.ChainWithLastIndexOf.lastIndexOf
is given below.
/** @return index of last occurrence of theElement,
* return -1 if theElement not in list */
public int lastIndexOf(Object theElement)
{
// search the chain for theElement
ChainNode currentNode = firstNode;
int index = 0; // index of currentNode
int indexToReturn = -1; // most recent index where theElement seen
while (currentNode != null)
{
if (currentNode.element.equals(theElement))
indexToReturn = index;
// move to next node
currentNode = currentNode.next;
index++;
}
return indexToReturn;
}
The complexity is Theta(size) because
every element of the chain is examined.