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

Finding Items in a List

Program gif 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.

   program9533
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 tex2html_wrap_inline60465, 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 tex2html_wrap_inline60791, where tex2html_wrap_inline60789 is the time required to do the comparison, and tex2html_wrap_inline60465 is the number of items in the ordered list. This simplifies to O(n) when the comparison can be done in constant time.


next up previous contents index

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