Types and Data Structures

7 pages · ~5 min✓ Reviewed

Start here. Next up: Functions and Closures.

PythonPage 1

Python Data Model at a Glance

1. Objects and Names

int float bool str bytes list tuple dict set frozenset NoneType
Every value is an object: id, type, value
Names are bound to objects, not boxes
b = a gives two names, one object

2. Mutable vs Immutable

	Mutable	Immutable
Types	list, dict, set, bytearray	int, str, tuple, frozenset, bytes
Change	in place	never: rebinds

python

a = [1]
b = a
b.append(2)
print(a, a is b)
s = t = "hi"
s += "!"
print(s, t)

s += rebinds s; t keeps the old object

output

[1, 2] True
hi! hi

== compares value; is compares identity
Use is only for None, True, False

3. Hashable

Hashable = __hash__ that never changes and agrees with __eq__
Built-in immutables: hashable; built-in mutable containers: not
User-class instances: hashable by identity by default
A tuple is hashable only if all items are
Only hashable objects: dict keys, set members

PythonPage 2

List and Tuple Operations and Costs

1. List = dynamic array

Cost	Operations
O(1)	`lst[i]`, `len`, `append`, `pop()` (amortized)
O(n)	`insert(0,x)`, `pop(0)`, `remove(x)`, `x in lst`

2. Methods and sorting

append(x) adds one item; extend(it) adds each item of it
insert(i,x) puts x at index i; remove(x) deletes the first match
pop(i=-1) removes and returns an item
sort() works in place and returns None
sorted(it) returns a new list
Stable Timsort, O(n log n)
key=len or key=lambda t: t[1] picks the field; reverse=True flips

python

pairs = [('a', 3), ('b', 1), ('c', 2)]
print(sorted(pairs, key=lambda t: t[1], reverse=True))
print(pairs.sort())

output

[('a', 3), ('c', 2), ('b', 1)]
None

3. Tuples

Immutable, fixed size: records, multiple return values, dict keys
Unpack: a, *rest = (1, 2, 3) gives rest == [2, 3]
One item needs a comma: (1,); (1) is just an int

Pops at both ends

Use collections.deque for O(1) pops at both ends; list.pop(0) is O(n).

PythonPage 3

Dict and Set Operations and Costs

1. Hash Tables

dict and set are hash tables
Lookup, insert, delete: O(1) average, O(n) worst case
dict keeps insertion order since 3.7

2. Access, Iterate, Merge

Tool	Effect
`d.get(k, default)`	default, no KeyError
`d.setdefault(k, [])`	inserts default if missing
`defaultdict(list)`	auto-creates missing values
`Counter(it)`	tallies items

Iterate: d.items(), d.keys(), d.values()
Merge: d | other or {**a, **b}

Mutating while iterating

Never add or remove keys while iterating. Loop over list(d) instead.

3. Set Operations

Op	Result
`a \| b`	union
`a & b`	intersection
`a - b`	difference
`a ^ b`	symmetric difference
`x in set`	O(1) vs O(n) for a list

PythonPage 4

Slicing and Comprehensions

1. Slice Rules

seq[start:stop:step], stop is exclusive
Negatives count from the end: s[-1] is the last item
Out-of-range bounds are clamped, never raise
A list slice copies: O(k) for k items

Idiom	Gives
`s[::-1]`	reversed copy
`s[:]`	shallow copy
`s[-3:]`	last three
`s[::2]`	every second item

2. Assignment and Immutables

lst[1:3] = [9] can resize the list
str and tuple slices return new objects (immutable)

python

lst = [1, 2, 3, 4]
lst[1:3] = [9]
print(lst)

output

[1, 9, 4]

3. Comprehensions

[f(x) for x in it if cond] builds a list
{k: v for ...} dict, {x for ...} set
(x for x in it) is a lazy generator, O(1) memory
Prefer it inside sum(), any(), all(): no temporary list

if vs else

A lone if goes after the loop. With else it moves before for: [a if c else b for x in it]

PythonPage 5

Copying and Truthiness

1. Assignment vs Copies

b = a copies nothing: two names, one object
Mutating through either name shows through both
copy.deepcopy(a): recursive, slower, handles cycles

Method	Outer	Inner
`b = a`	same	same
`a.copy()`, `list(a)`, `a[:]`, `copy.copy(a)`	new	shared
`copy.deepcopy(a)`	new	new

2. Truthiness

Falsy: None, False, 0, 0.0, '', [], (), {}, set(), range(0)
Everything else is truthy, even '0' and [0]

3. Shared-State Traps

def f(x=[]): default built once, shared by every call
Fix: x=None, then x = [] inside
[[0]*3]*3 repeats one inner row
Fix: [[0]*3 for _ in range(3)]

python

g = [[0]*3]*3
g[0][0] = 1
print(g[1][0])

output

Remember

Copies are shallow by default; nested edits need deepcopy.

PythonPage 6

Built-in Types Cheat Sheet

1. Mutability and Hashing

Type	Mutable	Hashable
list, dict, set	yes	no
tuple, str, frozenset, int	no	yes

Hashable = stable __hash__ that agrees with __eq__
A tuple is hashable only if all its items are
User-class instances: mutable yet hashable by identity

2. Costs and Slicing

Operation	Cost
list index	O(1)
`x in list`	O(n)
`x in dict` / `x in set`	O(1) average
`lst.insert(0, x)`	O(n)
sort	O(n log n)

s[a:b:c]: stop is exclusive
s[::-1] reverses
s[:] makes a shallow copy

3. Comprehensions, Copies, Truthiness

[x for ..] list, {k: v for ..} dict, {x for ..} set, (x for ..) lazy generator
b = a shares; a.copy() is shallow; copy.deepcopy(a) is full

Falsy: None, 0, '', empty containers
Test with if items:; None check is x is None

PythonPage 7

Check yourself

What do the two prints show?

[1] then [1, 2].
The default list is created once and shared. Use acc=None.

def f(x, acc=[]):
    acc.append(x)
    return acc
print(f(1))
print(f(2))

What does g print, and why?

[[1, 0], [1, 0]].
*2 repeats one inner row, so both rows are the same object. Use a comprehension.

g = [[0]*2]*2
g[0][0] = 1
print(g)

What does x hold?

None.
sort() sorts in place and returns None. sorted() returns a new list.

x = [3, 1, 2].sort()
print(x)