Python: How does "IN" (for lists) works?

Question

I have this code

list = ['a','b','c']

if 'b' in list:
   return "found it"
return "not found"

Now, how does this work? Does it traverse the whole list comparing the element? Does it use some kind of hash function?

Also, is it the same for this code?

list.index('b')

Answer 1

in uses the method __contains__. Each container type implements it differently. For a list, it uses linear search. For a dict, it uses a hash lookup.

Answer 2

Python Wiki states that val in list has O(n) average time complexity. This implies linear search. I expect list.index(val) to be the same.

After all, list is, well, a list. If you want hash tables, consider using set or dict.

Answer 3

The comparison is evaluated once for every item in the list.

See http://effbot.org/zone/python-list.htm for more information on Python lists (and list comprehensions as you have posted).

Answer 4

Both in and list.index() loop over all elements and have therefore a linear runtime. In addition to the intuitive logic (it has to be this way since a list is just a dynamic array), you can verify that by looking at the C implementation of list_contains (in) and listindex.

For example, the __contains__ routine is implemented as simple as:

static int
list_contains(PyListObject *a, PyObject *el)
{
    Py_ssize_t i;
    int cmp;

    for (i = 0, cmp = 0 ; cmp == 0 && i < Py_SIZE(a); ++i)
        cmp = PyObject_RichCompareBool(el, PyList_GET_ITEM(a, i),
                                           Py_EQ);
    return cmp;
}