Notes › Python
Python Lists, Dicts and Sets
List — ordered, mutable
a = [3, 1, 4]
a.append(1) # [3, 1, 4, 1]
a.insert(0, 9) # [9, 3, 1, 4, 1]
a.pop() # removes last → 1
a.pop(0) # removes index 0 → 9
a.remove(4) # removes first 4
a.sort() # in place
b = sorted(a, reverse=True) # new list
a.reverse(); a.index(3); a.count(1); len(a)
Slicing a[start:stop:step]:
s = [0, 1, 2, 3, 4, 5]
s[1:4] # [1, 2, 3]
s[:3] # [0, 1, 2]
s[-2:] # [4, 5]
s[::-1] # reversed copy
s[::2] # [0, 2, 4]
2D list: grid = [[0] * m for _ in range(n)] ✅ — not [[0] * m] * n ❌ (all rows would be the same list).
Tuple — ordered, immutable
p = (3, 4)
x, y = p # unpacking
point_set = {(0, 0), (1, 2)} # tuples can be set elements / dict keys
Dict — key → value
marks = {"asha": 90, "ravi": 75}
marks["neha"] = 88
marks.get("amit", 0) # 0 if missing (no KeyError)
"asha" in marks # True
del marks["ravi"]
for name, m in marks.items(): print(name, m)
list(marks.keys()); list(marks.values())
marks.setdefault("x", []).append(1)
Dicts keep insertion order (Python 3.7+).
Set — unique items, fast membership
s = {1, 2, 3}
s.add(4); s.discard(10) # discard: no error if missing
a, b = {1, 2, 3}, {2, 3, 4}
a | b # {1, 2, 3, 4} union
a & b # {2, 3} intersection
a - b # {1} difference
a ^ b # {1, 4} symmetric difference
Empty set is set() — {} is an empty dict.
Complexity
| Operation | list | dict / set |
|---|---|---|
| Index access | O(1) | — |
x in ... |
O(n) | O(1) average |
| append / add | O(1) amortised | O(1) average |
| insert/pop at front | O(n) | — |
| pop from end | O(1) | — |
| sort | O(n log n) | — |
So for "have I seen this?" use a set, not a list.
Comprehensions
squares = [x * x for x in range(10)]
evens = [x for x in nums if x % 2 == 0]
pairs = [(i, j) for i in range(3) for j in range(3) if i != j]
lengths = {w: len(w) for w in words} # dict comprehension
unique_lower = {w.lower() for w in words} # set comprehension
gen = (x * x for x in range(10**6)) # generator: lazy, low memory
The collections module (DSA favourites)
from collections import Counter, defaultdict, deque, OrderedDict
import heapq, bisect
Counter("banana") # {'a': 3, 'n': 2, 'b': 1}
Counter(words).most_common(3) # top 3
graph = defaultdict(list) # no KeyError for new keys
graph[u].append(v)
q = deque([1, 2])
q.appendleft(0); q.append(3) # O(1) at both ends
q.popleft() # use for BFS (list.pop(0) is O(n))
h = [] # heapq = min-heap
heapq.heappush(h, 5); heapq.heappush(h, 1)
heapq.heappop(h) # 1
heapq.nlargest(2, nums)
bisect.bisect_left([1, 3, 5], 4) # 2 → binary search insertion point
Sorting with keys
students.sort(key=lambda s: (-s["marks"], s["name"])) # marks desc, then name asc
max(words, key=len)
Copying
import copy
b = a[:] # shallow copy (or list(a), a.copy())
c = copy.deepcopy(a) # copies nested lists too
Interview one-liners
- Lists are dynamic arrays; dicts and sets are hash tables.
- Membership in a list is O(n), in a set/dict O(1) average.
dequefor queues,heapqfor priority queues,Counterfor frequencies.- Dict keys must be hashable (immutable): str, int, tuple — not list.