Why is a list access O(1) in Python?

Question

I understand that a list is different from an array. But still, O(1)? That would mean accessing an element in a list would be as fast as accessing an element in a dict, which we all know is not true. My question is based on this document:

list

----------------------------
| Operation | Average Case |
|-----------|--------------|
|    ...    |     ...      |
|-----------|--------------|
|  Get Item |     O(1)     |
----------------------------

and this answer:

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure.

If the first document is true, then why is accessing a dict faster than accessing a list if they have the same complexity?

Can anybody give a clear explanation on this please? I would say it always depends on the size of the list/dict, but I need more insight on this.

Solution 1

Get item is getting an item in a specific index, while lookup means searching if some element exists in the list. To do so, unless the list is sorted, you will need to iterate all elements, and have O(n) Get Item operations, which leads to O(n) lookup.

A dictionary is maintaining a smart data structure (hash table) under the hood, so you will not need to query O(n) times to find if the element exists, but a constant number of times (average case), leading to O(1) lookup.

Solution 2

accessing a list l at index n l[n] is O(1) because it is not implemented as a Vanilla linked list where one needs to jump between pointers (value, next-->) n times to reach cell index n.

If the memory is continuous and the entry size would had been fixed, reaching a specific entry would be trivial as we know to jump n times an entry size (like classic arrays in C).

However, since list is variable in entries size, the python implementation uses a continuous memory list just for the pointers to the values. This makes indexing a list (l[n]) an operation whose cost is independent of the size of the list or the value of the index.

For more information see http://effbot.org/pyfaq/how-are-lists-implemented.htm

Solution 3

That is because Python stores the address of each node of a list into a separate array. When we want an element at nth node, all we have to do is look up the nth element of the address array which gives us the address of nth node of the list by which we can get the value of that node in O(1) complexity.

Python does some neat tricks to make these arrays expandable as the list grows. Thus we are getting the flexibility of lists and and the speed of arrays. The trade off here is that the compiler has to reallocate memory for the address array whenever the list grows to a certain extent.

amit has explained in his answer to this question about why lookups in dictionaries are faster than in lists.