|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
defines the IsMember
and Find methods of the ListAsLinkedList class.
The implementations of these methods are almost identical.
However, they differ in two key aspects--the comparison used and the return value.
Program: OrderedListAsLinkedList class IsMember and Find methods.
The IsMember method tests whether
a particular object instance is contained in the ordered list.
It returns a bool value indicating whether the object is present.
The running time of this method is clearly O(n),
where 
,
the number of items in the ordered list.
The Find method locates an object
which matches a given object.
The match is determined by using the overloaded == operator.
Find returns a reference to the matching object if one is found.
Otherwise, it returns the null value.
The running time for this method,
is 
,
where 
is the time required to do the comparison,
and is the number of items in the ordered list.
This simplifies to O(n) when the comparison can be done in constant time.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.