|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
defines the __contains__
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 __contains__ and find methods.
The __contains__ 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 == operator.
find returns a reference to the matching object if one is found.
Otherwise, it returns None.
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 © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.