Logo 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 member functions of the ListAsLinkedList class. The implementations of these functions are almost identical. However, they differ in two key aspects--the comparison used and the return value.

   program10173
Program: ListAsLinkedList Class IsMember and Find Member Function Definitions

The IsMember function tests whether a particular object instance is contained in the ordered list. It returns a Boolean value indicating whether the object is present. The running time of this function is clearly O(n), where tex2html_wrap_inline61308, the number of items in the ordered list.

The Find member function locates an object which matches a given object. The match is determined by using operator==. Find returns a reference to the matching object if one is found. Otherwise, it returns a reference to the NullObject instance. The running time for this function, is tex2html_wrap_inline61650, where tex2html_wrap_inline61648 is the time required to do the comparison, and tex2html_wrap_inline61308 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 © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.