Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Removing Items from a List

Objects are removed from a searchable container using the Withdraw method. Program gif defines the Withdraw method for the OrderedListAsArray class. This method takes a single argument which is a the object to be removed from the container. It is the specific object instance which is removed from the container, not simply one which matches (i.e., compares equal to) the argument.

   program8857
Program: OrderedListAsArray class Withdraw method.

The withdraw method first needs to find the position of the item to be removed from the list. An exception is thrown if the list is empty, or if the object to be removed is not in the list. The number of iterations needed to find an object depends on its position. If the object to be removed is found at position i, then the search phase takes O(i) time.

Removing an object from position i of an ordered list which is stored in an array requires that all of the objects at positions i+1, i+2, ..., tex2html_wrap_inline60457, be moved one position to the left. Altogether, tex2html_wrap_inline60809 objects need to be moved. Hence, this phase takes tex2html_wrap_inline60811 time.

The running time of the Withdraw method is the sum of the running times of the two phases, O(i)+ tex2html_wrap_inline60811. Hence, the total running time is O(n), where tex2html_wrap_inline60465 is the number of items in the ordered list.

Care must be taken when using the Withdraw method. Consider the following:

ComparableInt32 object1 = 57;
ComparableInt32 object2 = 57;
List list = new OrderedListAsArray(1);
list.Insert(object1);
To remove object1 from the ordered list, we may write
list.Withdraw(object1);
However, the call
list.Withdraw(object2);
will fail because object2 is not actually in the list. If for some reason we have lost track of object1, we can always write:
list.Withdraw(list.Find(object2));
which first locates the object in the ordered list (object1) which matches object2 and then deletes that object.


next up previous contents index

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