Following on from the C++ collections post, it’s time to create a similar overview page for Python! There are more collection classes than this, but I wanted to revise the basics.
Common features
Common Python sequence operations are documented here.
Overview
| list | array | deque |
| set | dict | stack |
| queue | tuple |
list
A variable sized array where elements do not need to all be the same type. \(O(1)\) to access an element, and \(O(1)\) amortized for adding an element at the end.
l = [3, 6, 34, 1]
for element in l:
print(element)
print(l[2])
# add item to end
l.append(10)
# add multiple items to end
l.extend([9, 0, -1])
# insert at position 2
l.insert(2, 'string')
# remove item by value
l.remove(34)
# remove last item in list and return it
# pop can also take an index
print(l.pop()) # 1
# delete first element of the list
del l[0]
print(l) # [6, 'string', 1, 10, 9, 0]
# clear the contents of the list
copy = l.copy()
l.clear()
print(copy) # [6, 'string', 1, 10, 9, 0]
array
A list where all elements are constrained to be the same type. The interface for the array is very similar to that of a list.
from array import array
# signed long array
a = array('l', [3, 4, 5, 6, 9])
deque
Similar to a list, but provides approximately \(O(1)\) performance for removal from the beginning or end of the list. The interface is similar to a list, but with a number of left functions to allow fast operations on the left of the deque.
from collections import deque
d = deque([3, 6, 34, 1])
for element in d:
print(element)
print(d.pop()) # 1
print(d.popleft()) # 3
d.append(-12)
d.appendleft(5)
print(d) # deque([5, 6, 34, -12])
d.extend([7, 7])
d.extendleft([2, 2])
print(d) # deque([2, 2, 5, 6, 34, -12, 7, 7])
set
An unordered set of unique elements. set is implemented using a hash table and provides \(O(1)\) access to elements.
s = { 2, 3, 4, 5, 5}
print(s) # {2, 3, 4, 5}
s = set([3, 2, 1, 2])
print(s) # {1, 2, 3}
print(0 in s) # False
print(3 in s) # True
s.remove(2)
print(s) # {1, 3}
dict
Associative containers that hold key-value pairs. dict is \(O(1)\) for insertion, removal and search.
d = { 'day': 'Tuesday', 10: 123 }
for key, value in d.items():
print('{}: {}'.format(key, value))
# default iterator is over keys
for key in d:
print(key)
del d['day']
print(d) # {10: 123}
stack
Stacks can be implemented in Python using a list.
stack = []
# append == push
stack.append(10)
stack.append(12)
print(stack.pop()) # 12
queue
Queues can be implemented efficiently using a deque.
from collections import deque
queue = deque()
# append == enqueue
queue.append(12)
queue.append(24)
# popleft == dequeue
print(queue.popleft()) # 12
tuple
Tuples are immutable sequences. They can be used as keys for a dict and also can be unpacked easily. namedtuple also allows the elements of the tuple to be assigned names.
from collections import namedtuple
t = (1, 2, 3)
a, b, c = t
print('a: {} b: {} c: {}'.format(a, b, c))
Test = namedtuple('Test', ['a', 'b'])
t2 = Test(4, 5)
print(t2.a) # 4