Many programmers easily confuse Python's list type with the concept of linked lists found often in standard libraries of other languages such as C, C++, or Java. In fact, CPython lists are not lists at all. In CPython, lists are implemented as variable length arrays. This should also be true for other implementations such as Jython and IronPython, although such implementation details are often not documented in these projects. The reasons for such confusion are clear. This datatype is named list and also has an interface that could be expected from any linked list implementation.

Why is it important and what does it mean? Lists are one of the most popular data structures and the way they are used greatly affects every application's performance. Also, CPython is the most popular and used implementation, so knowing its internal implementation details is crucial.

In detail, lists in Python is a contiguous array of references to other objects. The pointer to this array and the length is stored in a lists head structure. This means that every time an item is added or removed, the array of references needs to be resized (reallocated). Fortunately, in Python, these arrays are created with exponential over-allocation, so not every operation requires a resize. This is how the amortized cost of appending and popping elements can be low in terms of complexity. Unfortunately, some other operations that are considered "cheap" in ordinary linked lists have relatively high computational complexity in Python:

Here, n is the length of a list. At least retrieving or setting an element using index is an operation that cost is independent of the list's size. Here is a full table of average time complexities for most of the list operations:

For situations where a real linked list is needed (or simply, a data structure that has appends and pop at each side at O(1) complexity), Python provides deque in collections built-in module. This is a generalization of stacks and queues and should work fine anywhere where a doubly linked list is required.

As you probably know, writing a piece of code such as this is painful:

>>> evens = []
>>> for i in range(10):
... if i % 2 == 0:
... evens.append(i)
... 
>>> evens
[0, 2, 4, 6, 8]

This may work for C, but it actually makes things slower for Python because:

A list comprehension is the correct answer to this pattern. It uses wired features that automate parts of the previous syntax:

>>> [i for i in range(10) if i % 2 == 0]
[0, 2, 4, 6, 8]

Besides the fact that this writing is more efficient, it is way shorter and involves fewer elements. In a bigger program, this means fewer bugs and code that is easier to read and understand.

Another typical example of a Python idiom is the usage of enumerate. This built-in function provides a convenient way to get an index when a sequence is used in a loop. Consider the following piece of code as an example:

>>> i = 0
>>> for element in ['one', 'two', 'three']:
... print(i, element)
... i += 1
...
0 one
1 two
2 three

This can be replaced by the following code, which is shorter:

>>> for i, element in enumerate(['one', 'two', 'three']):
... print(i, element)
...
0 one
1 two
2 three

When the elements of multiple lists (or any iterables) need to be aggregated in a one-by-one fashion, then the built-in zip() function may be used. This is a very common pattern for uniform iteration over two same-sized iterables:

>>> for item in zip([1, 2, 3], [4, 5, 6]):
... print(item)
... 
(1, 4)
(2, 5)
(3, 6)

Note that the results of zip() can be reversed by another zip() call:

>>> for item in zip(*zip([1, 2, 3], [4, 5, 6])):
... print(item)
... 
(1, 2, 3)
(4, 5, 6)

Another popular syntax element is sequence unpacking. It is not limited to lists and tuples and will work with any sequence type (even strings and byte sequences). It allows you to unpack a sequence of elements into another set of variables as long as there are as many variables on the left-hand side of the assignment operator as the number of elements in the sequence:

>>> first, second, third = "foo", "bar", 100
>>> first
'foo'
>>> second
'bar'
>>> third
100

Unpacking also allows you to capture multiple elements in a single variable using starred expressions as long as it can be interpreted unambiguously. Unpacking can also be performed on nested sequences. This can come in handy especially when iterating on some complex data structures built of sequences. Here are some examples of more complex unpacking:

>>> # starred expression to capture rest of the sequence
>>> first, second, *rest = 0, 1, 2, 3
>>> first
0
>>> second
1
>>> rest
[2, 3]

>>> # starred expression to capture middle of the sequence
>>> first, *inner, last = 0, 1, 2, 3
>>> first
0
>>> inner
[1, 2]
>>> last
3

>>> # nested unpacking
>>> (a, b), (c, d) = (1, 2), (3, 4)
>>> a, b, c, d
(1, 2, 3, 4)

CPython uses hash tables with pseudo-random probing as an underlying data structure for dictionaries. It seems like a very deep implementation detail, but it is very unlikely to change in the near future, so it is also a very interesting fact for the programmer.

Due to this implementation detail, only objects that are hashable can be used as a dictionary key. An object is hashable if it has a hash value that never changes during its lifetime and can be compared to different objects. Every Python's built-in type that is immutable is also hashable. Mutable types such as list, dictionaries, and sets are not hashable and so they cannot be used as dictionary keys. Protocol that defines if a type is hashable consists of two methods:

Two objects that are compared equal must have the same hash value. The reverse does not need to be true. This means collisions of hashes are possible—two objects with the same hash may not be equal. It is allowed, and every Python implementation must be able to resolve hash collisions. CPython uses open addressing to resolve such collisions (https://en.wikipedia.org/wiki/Open_addressing). Still, the probability of collisions greatly affects performance, and if it is high, the dictionary will not benefit from its internal optimizations.

While three basic operations: adding, getting, and deleting an item have an average time complexity equal to O(1), their amortized worst case complexities are a lot higher—O(n), where n is the current dictionary size. Additionally, if user-defined class objects are used as dictionary keys and they are hashed improperly (with a high risk of collisions), then this will have a huge negative impact on the dictionary performance. The full table of CPyhton's time complexities for dictionaries is as follows:

It is also important to know that the n number in worst-case complexities for copying and iterating the dictionary is the maximum size that the dictionary ever achieved, rather than the current item count. In other words, iterating over the dictionary that once was huge but has greatly shrunk in time may take a surprisingly long time. So, in some cases, it may be better to create a new dictionary object if it has to be iterated often instead of just removing elements from the previous one.

One of the common pitfalls of using dictionaries is that they do not preserve the order of elements in which new keys were added. In some scenarios, when dictionary keys use consecutive keys whose hashes are also consecutive values (for example, using integers), the resulting order might be the same due to the internal implementation of dictionaries:

>>> {number: None for number in range(5)}.keys()
dict_keys([0, 1, 2, 3, 4])

Still, using other datatypes which hash differently shows that the order is not preserved. Here is an example in CPython:

>>> {str(number): None for number in range(5)}.keys()
dict_keys(['1', '2', '4', '0', '3'])
>>> {str(number): None for number in reversed(range(5))}.keys()
dict_keys(['2', '3', '1', '4', '0'])

As shown in the preceding code, the resulting order is both dependent on the hashing of the object and also on the order in which the elements were added. This is not what can be relied on because it can vary with different Python implementations.

Still, in some cases, the developer might need dictionaries that preserve the order of additions. Fortunately, the Python standard library provides an ordered dictionary called OrderedDict in the collections module. It optionally accepts an iterable as the initialization argument:

>>> from collections import OrderedDict
>>> OrderedDict((str(number), None) for number in range(5)).keys()
odict_keys(['0', '1', '2', '3', '4'])

It also has some additional features such as popping items from both ends using the popitem() method or moving the specified element to one of the ends using the move_to_end() method. A full reference on that collection is available in the Python documentation (refer to https://docs.python.org/3/library/collections.html).

The other important note is that in very old code bases, dict may be used as a primitive set implementation that ensures the uniqueness of elements. While this will give proper results, this should be omitted unless Python versions lower than 2.3 are targeted. Using dictionaries this way is wasteful in terms of resources. Python has a built-in set type that serves this purpose. In fact, it has a very similar internal implementation to dictionaries in CPython, but offers some additional features as well as specific set-related optimizations.

Sets in CPython are very similar to dictionaries. As a matter of fact, they are implemented like dictionaries with dummy values, where only keys are actual collection elements. Also, sets exploit this lack of values in mapping for additional optimizations.

Thanks to this, sets allow very fast additions, deletions, and checking for element existence with the average time complexity equal to O(1). Still, since the implementation of sets in CPython relies on a similar hash table structure, the worst-case complexity for these operations is O(n), where n is the current size of a set.

Other implementation details also apply. The item to be included in a set must be hashable, and if instances of user-defined classes in a set are hashed poorly, this will have a negative impact on the performance.