Built in data structures
- int
- float
- bool
- str
- bytes
- bytearray
- complex
Main Built in collections
- list
- tuple
- set
- frozenset
- dict
Standard Library Collections
- deque
- namedtuple
- defaultdict
- OrderedDict
- Counter
- ChainMap
Other Useful Built-in/stdlib Containers
- array.array
- memoryview
- range
Time complexities (average / amortized unless noted)
n = number of elements, k = number of distinct keys (for maps), i = index
Sequence / list-like
| Type | index access | append | pop() end | pop(i) / insert(i, x) | search (x in) | slicing |
|---|
list | O(1) | amortized O(1) | amortized O(1) | O(n) | O(n) | O(k) to build slice |
tuple | O(1) | — (immutable) | — | — | O(n) | O(k) to build new tuple |
range | O(1) for index & in (uses arithmetic) | — | — | — | O(1) / O(log n) depending on value check | — |
array.array | O(1) | amortized O(1) | amortized O(1) | O(n) | O(n) | O(k) |
Mapping / associative
| Type | get/set by key | delete | in key | iteration order |
|---|
dict | average O(1) | average O(1) | O(1) | insertion order (CPython 3.7+) |
defaultdict | same as dict | same | same | same |
mappingproxy | O(1) (read-only view) | — | O(1) | same as underlying dict |
ChainMap | lookup O(m) worst-case (search chains) | mutating affects first map | same | order per underlying maps |
Set-like
| Type | add | remove (discard) | membership | iteration |
|---|
set | average O(1) | average O(1) | average O(1) | O(n) |
frozenset | immutable (hashable) | — | O(1) | O(n) |
Counter | update O(k) | decrement O(1) | O(1) membership for keys | O(k) over distinct keys |
collections specialized
| Type | notes |
|---|
deque | append/pop both ends O(1); random access O(n) |
namedtuple | like tuple (O(1) access by index), plus named fields (attribute lookup O(1)) |
OrderedDict | same as dict in modern Python; historically maintained order (extra methods) |
defaultdict | dict + automatic default factory |
Memory / views
| Type | notes |
|---|
memoryview | O(1) slicing/viewing, zero-copy into bytes/bytearray |
bytes | immutable sequence of bytes (indexing O(1)) |
bytearray | mutable bytes (indexing O(1)) |