Trade-offs with Data Types

Lists

Lists are implemented like “stacks”. It’s very inexpensive to add things to the end of a list or remove things from the end of a list:

>>> numbers = [2, 1, 3, 4]
>>> numbers.append(7)
>>> numbers.pop()
7

It’s expensive to add to or remove from the beginning of a list, because the list needs to shuffle everything to make room for the new item or remove the gap of the item removed.

>>> numbers.pop(0)
2
>>> numbers.insert(0, 2)

It’s expensive to ask whether a list contains something; Python has to search through the list to find if it’s there.

>>> 5 in numbers
False

Because lists are indexable, if you have an index of something in the list, it’s very inexpensive to access it or modify it.

>>> numbers[-1]
4
>>> numbers[-1] = 11

Sets and Dictionaries

Sets and dictionaries are implemented using hash tables.

>>> d = {1: 'a'}
>>> s = {2}

It’s inexpensive to add to or remove items from a dictionary or set:

>>> d.pop(1)
'a'
>>> d[3] = 'c'
>>> s.pop()
2
>>> s.add(3)

Because hashing is quick, it’s inexpensive to ask whether a set contains something; it only needs to do the one calculation and it’s either there or not there.

>>> 4 in s
False
>>> 3 in s
True

Likewise, it’s also inexpensive to ask whether a dictionary contains certain keys.

>>> 4 in d
False
>>> 3 in d
True

It’s also inexpensive to change the value of a dictionary key.

>>> d[3] = 'b'