How exactly does Python check through a list?

I was doing one of the course exercises on codeacademy for python and I had a few questions I couldn't seem to find an answer to:

For this block of code, how exactly does python check whether something is "in" or "not in" a list? Does it run through each item in the list to check or does it use a quicker process?

Also, how would this code be affected if it were running with a massive list of numbers (thousands or millions)? Would it slow down as the list size increases, and are there better alternatives?

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  for i in list: 
    if i not in new_list:
      new_list.append(i)
  return new_list

remove_duplicates(numbers)

Thanks!

P.S. Why does this code not function the same?

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  new_list.append(i for i in list if i not in new_list)
  return new_list

Solution

In order to execute i not in new_list Python has to do a linear scan of the list. The scanning loop breaks as soon as the result of the test is known, but if i is actually not in the list the whole list must be scanned to determine that. It does that at C speed, so it's faster than doing a Python loop to explicitly check each item. Doing the occasional in some_list test is ok, but if you need to do a lot of such membership tests it's much better to use a set.

On average, with random data, testing membership has to scan through half the list items, and in general the time taken to perform the scan is proportional to the length of the list. In the usual notation the size of the list is denoted by n, and the time complexity of this task is written as O(n).

In contrast, determining membership of a set (or a dict) can be done (on average) in constant time, so its time complexity is O(1). Please see TimeComplexity in the Python Wiki for further details on this topic. Thanks, Serge, for that link.

Of course, if your using a set then you get de-duplication for free, since it's impossible to add duplicate items to a set.

One problem with sets is that they generally don't preserve order. But you can use a set as an auxilliary collection to speed up de-duping. Here is an illustration of one common technique to de-dupe a list, or other ordered collection, which does preserve order. I'll use a string as the data source because I'm too lazy to type out a list. ;)

new_list = []
seen = set()
for c in "this is a test":
    if c not in seen:
        new_list.append(c)
        seen.add(c)
print(new_list)

output

['t', 'h', 'i', 's', ' ', 'a', 'e']

Please see How do you remove duplicates from a list whilst preserving order? for more examples. Thanks, Jean-François Fabre, for the link.

As for your PS, that code appends a single generator object to new_list, it doesn't append what the generate would produce.

I assume you alreay tried to do it with a list comprehension:

new_list = [i for i in list if i not in new_list]

That doesn't work, because the new_list doesn't exist until the list comp finishes running, so doing in new_list would raise a NameError. And even if you did new_list = [] before the list comp, it won't be modified by the list comp, and the result of the list comp would simply replace that empty list object with a new one.

BTW, please don't use list as a variable name (even in example code) since that shadows the built-in list type, which can lead to mysterious error messages.