Python data structure complexities

Python list

The List ADT is internally represented by an Array

The costly operations are inserting and deleting items near the beginning (as everything has to be moved). Insert at the end also becomes costly if preallocated space becomes full.

Operation	Examples	Average Case	Amortised Worst Case
Append	l.append(item)	$O(1)$	$O(1)$
Clear	l.clear()	$O(1)$	$O(1)$
Containment	item in/not in l	$O(N)$	$O(N)$
Copy	l.copy()	$O(N)$	$O(N)$
Delete	del l[i]	$O(N)$	$O(N)$
Extend	l.extend(…)	$O(N)$	$O(N)$
Equality	l1==l2, l1!=l2	$O(N)$	$O(N)$
Index	l[i]	$O(1)$	$O(1)$
Iteration	for item in l:	$O(N)$	$O(N)$
Length	len(l)	$O(1)$	$O(1)$
Multiply	k*l	$O(k\ast N)$	$O(k\ast N)$
Min, Max	min(l), max(l)	$O(N)$	$O(N)$
Pop from end	l.pop(-1)	$O(1)$	$O(1)$
Pop intermediate	l.pop(item)	$O(N)$	$O(N)$
Remove	l.remove(…)	$O(N)$	$O(N)$
Reverse	l.reverse()	$O(N)$	$O(N)$
Slice	l[x:y]	$O(y-x)$	$O(y-x)$
Sort	l.sort()	$O(N\ast log(N))$	$O(N\ast log(N))$
Store	l[i]=item	$O(1)$	$O(1)$

Python dict

Python implements the Dictionary ADT using a Hash table

Operation	Examples	Average Case	Amortised Worst Case
Clear	d.clear()	$O(1)$	$O(1)$
Construction	dict(...)	$O(len(d))$	$O(len(d))$
Delete	del d[k]	$O(1)$	$O(N)$
Get	d.get()	$O(1)$	$O(N)$
Iteration(key, value, item)	for item in d:	$O(N)$	$O(N)$
Length	len(d)	$O(1)$	$O(1)$
Pop	d.pop(item)	$O(1)$	$O(N)$
Pop Item	d.popitem()	$O(1)$	$O(1)$
Returning Views	d.values()	$O(1)$	$O(1)$
Returning keys	d.keys()	$O(1)$	$O(1)$
Fromkeys	d.fromkeys(seq)	$O(len(seq))$	$O(len(seq))$

Python set

Python implements the Set ADT using a Hash table

The major advantage of using a Set, as opposed to a List, is that it has a highly optimised method for checking whether a specific element is contained in the set (using the hash table)

Operation	Examples	Average Case	Amortised Worst Case
Add	s.add(item)	$O(1)$	$O(N)$
Clear	s.clear()	$O(1)$	$O(1)$
Copy	s.copy()	$O(N)$	$O(N)$
Containment	item in/not in s	$O(1)$	$O(N)$
Creation	set(…)	$O(len(s))$	$O(len(s))$
Discard	s.discard(item)	$O(1)$	$O(N)$
Difference	s1-s2	$O(len(s1))$	$O(len(s1))$
Difference Update	s1.difference_update(s2)	$O(len(s2))$	$-$
Equality	s1==s2, s1!=s2	$O(min(len(s1),len(s2)))$	$O(min(len(s1),len(s2)))$
Intersection	s1 & s2	$O(min(len(s1),len(s2)))$	$O(min(len(s1),len(s2)))$
Iteration	for item in s:	$O(N)$	$O(N)$
Is Subset	s1<=s2	$O(len(s1))$	$O(len(s1))$
Is Superset	s1>=s2	$O(len(s2))$	$O(len(s1))$
Pop	s.pop()	$O(1)$	$O(N)$
Union	s1|s2	$O(len(s1)+len(s2))$	$-$
Symmetric Difference	s1^s2	$len(s1)$	$O(len(s1)\ast len(s2))$

---

Sources: 1, 2

• task Transcribe screenshots