|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
The purpose of the Withdraw method is to remove
an item from the sorted list.
Program 
defines the Withdraw
method which takes an object and removes it from the sorted list.
Program: SortedListAsArray class Withdraw method.
The Withdraw method makes use of FindOffset
to determine the array index of the item to be removed.
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, ..., 
,
be moved one position to the left.
The worst case is when i=0.
In this case, items need to be moved to the left.
Although the Withdraw method is able to make
use of FindOffset to locate the position
of the item to be removed in 
time,
the total running time is dominated by the left shift,
which is O(n) in the worst case.
Therefore, the running time of Withdraw is O(n).
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.