Finding Items in a List

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Finding Items in a List

Program defines two OrderedListAsArray class methods which search for an object in the ordered list. The __contains__ method tests whether a particular object instance is in the ordered list. The find method locates in the list an object which matches its argument.

program8692
Program: OrderedListAsArray class __contains__ and find methods.

The __contains__ method is a bool-valued method. In addition to self, the __contains__ method takes a single argument, obj. This method compares the argument one-by-one with the contents of the _array. Note that this method tests whether a particular object instance is contained in the ordered list using the Python is operator. In the worst case, the object sought is not in the list. In this case, the running time of the method is O(n), where is the number of items in the ordered list.

The find method also does a search of the ordered list. However, it uses the == operator to compare the items. Thus, the Find method searches the list for an object which matches its argument. The Find method returns the object found. If no match is found, it returns None. The running time of this method depends on the time required for the comparison operator, . In the worst case, the object sought is not in the list. In this case the running time is . For simplicity, we will assume that the comparison takes a constant amount of time. Hence, the running time of the method is also O(n), where is the number of items in the list.

It is important to understand the subtle distinction between the search done by the __contains__ method and that done by find. The __contains__ method searches for a specific object instance while find simply looks for a matching object. Consider the following:

obj1 = [57]
obj2 = [57]
list = OrderedListAsArray(1)
list.insert(obj1)

This code fragment creates two tuples, both of which contain a single integer, 57. Only the first object, obj1, is inserted into the ordered list list. Consequently, evaluating the expression

obj1 in list

results in the value true; whereas evaluating the expression

obj2 in list

results in the value false.

On the other hand, if a search is done using the find method like this:

obj3 = list.find(obj2)

the search will be successful! After the call, obj3 and obj1 refer to the same object.