extract Method

In this section we consider the extract method of the LinkedList class. The purpose of this method is to delete the specified element from the linked list.

  
Program: LinkedList class extract method.

The extract method searches sequentially for the item to be deleted. In the absence of any a priori knowledge, we do not know in which list element the item to be deleted will be found. In fact, the specified item may not even appear in the list!

If we assume that the item to be deleted is in the list, and if we assume that there is an equal probability of finding it in each of the possible positions, then on average we will need to search half way through the list before the item to be deleted is found. In the worst case, the item will be found at the tail--assuming it is in the list.

If the item to be deleted does not appear in the list, the algorithm shown in Program  throws an IllegalArgumentException  exception . A simpler alternative might be to do nothing--after all, if the item to be deleted is not in the list, then we are already done! However, attempting to delete an item which is not there, is more likely to indicate a logic error in the programming. It is for this reason that an exception is thrown.

In order to determine the running time of the extract method, we first need to determine the time to find the element to be deleted. If the item to be deleted is not in the list, then the running time of Program  up to the point where it throws the exception (line 14) is T(n)=O(n).

Now consider what happens if the item to be deleted is found in the list. In the worst-case the item to be deleted is at the tail. Thus, the running time to find the element is O(n). Actually deleting the element from the list once it has been found is a short sequence of relatively straight-forward manipulations. These manipulations can be done in constant time. Therefore, the total running time is T(n)=O(n).

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.