These are the notes for Python episode 35, part two of data structures and algorithms. Raju's VIP orders must jump to the front of a long order list, and insert(0) is slow because a list is an array (episode 34). So you invent the linked list: nodes joined by links, where adding at the front is one step. Then Raju needs to find a customer among a million by phone number. Checking one by one is O(n), and one slot per phone number runs out of memory, so you invent hashing: the idea behind Python's dict and set. Every program below ran for real (Python 3.13.18). Timings vary by computer; compare the patterns.
The problem: VIP orders at the front
import time
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
n = 100_000
start = time.perf_counter()
lst = []
for i in range(n):
lst.insert(0, i) # shift everyone
print(f"list.insert(0): {time.perf_counter() - start:.3f} s")
start = time.perf_counter()
head = None
for i in range(n):
head = Node(i, head) # one new link
print(f"linked push_front: {time.perf_counter() - start:.3f} s")
Output (one run):
list.insert(0): 0.879 s
linked push_front: 0.022 s
The list keeps items side by side, so every insert at the front shifts everything: O(n) each, O(n²) for the loop. The linked version (below) does the same job about 40× faster here, and the gap grows with n.
The linked list
Real-life picture: an Indian Railways train.
| Train | Linked list | In code |
|---|---|---|
| A coach with passengers and a coupling to the next coach | node | value + next |
| The engine, where the train starts | head | the first node |
| The last coach, nothing behind it | the end | next = None |
| Add a coach at the front: one new coupling, nobody moves | push_front | O(1) |
A node is a small object holding a value and next, a reference (an arrow) to the next node. A linked list is a chain of nodes. You only keep head; every other node is reached by following next.
Building and walking a train
class Node:
def __init__(self, value):
self.value = value
self.next = None # the coupling to the next coach
engine = Node("engine")
a = Node("A1")
b = Node("B1")
engine.next = a # couple them
a.next = b
coach = engine
while coach is not None: # walk the train
print(coach.value, end=" -> ")
coach = coach.next
print("None")
Output:
engine -> A1 -> B1 -> None
The while node is not None: ... node = node.next loop is the walk (also called traversal). Almost every linked-list operation is a walk.
A LinkedList class
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def push_front(self, value): # O(1): one new link
self.head = Node(value, self.head)
def __str__(self):
parts, node = [], self.head
while node: # walk: O(n)
parts.append(node.value)
node = node.next
return " -> ".join(parts) + " -> None"
orders = LinkedList()
for o in ["toast", "samosa", "chai"]:
orders.push_front(o)
print(orders)
print(orders[0])
Output:
chai -> samosa -> toast -> None
Traceback (most recent call last):
File "main.py", line 22, in <module>
print(orders[0])
~~~~~~^^^
TypeError: 'LinkedList' object is not subscriptable
push_front makes a new node whose next is the old head, then moves head to it. Subscriptable means "supports [ ] indexing". A linked list has no numbered slots, so there is no instant index: to reach the k-th item you walk k steps, O(k). (You could add __getitem__ that walks, but it would still be O(n).)
Walking past the end
class Node:
def __init__(self, value):
self.value = value
self.next = None
head = Node("chai")
head.next = Node("samosa")
node = head
for _ in range(3): # one step too many
print(node.value)
node = node.next
Output:
chai
samosa
Traceback (most recent call last):
File "main.py", line 11, in <module>
print(node.value)
^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'value'
After the last node, node is None, and None has no .value. Walk with while node is not None, not a fixed count.
Removing a node: relink around it
To remove samosa from chai → samosa → toast, stand on the node before it and point its next past it: chai.next = chai.next.next. Nothing refers to samosa any more, so Python's garbage collector frees it. Nothing shifts.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def show(node):
while node:
print(node.value, end=" -> ")
node = node.next
print("None")
def remove(head, value): # returns the new head
if head and head.value == value:
return head.next
node = head
while node and node.next:
if node.next.value == value:
node.next = node.next.next # skip over it
return head
node = node.next
return head
head = Node("chai", Node("samosa", Node("toast")))
show(head)
head = remove(head, "samosa")
show(head)
head = remove(head, "chai")
show(head)
Output:
chai -> samosa -> toast -> None
chai -> toast -> None
toast -> None
Removing the head is O(1). Removing anything else costs the walk to find it, O(n).
Array list vs linked list
| Operation | Python list (dynamic array) | Linked list |
|---|---|---|
| Get item i | O(1) | O(n): walk |
| Add/remove at the front | O(n): shift | O(1) |
| Add at the end | O(1) amortized | O(1) with a tail pointer, else O(n) |
| Find a value | O(n) | O(n) |
| Remove a node you're already standing before | O(n): shift | O(1): relink |
| Memory | compact | one extra reference per node |
Variants: a doubly linked list has prev and next (walk both ways, remove a known node in O(1)); a circular list's last node points back to the head. collections.deque (episode 34) is a doubly linked list of blocks, so in everyday Python you rarely write your own linked list. You will in interviews, and inside other structures, like hash table buckets.
The next problem: find a customer by phone
A customer calls from 9876543210. Raju has 1,000,000 customers. A list or a linked list checks them one by one: O(n). An array index is O(1), so the obvious idea: use the phone number as the index.
print("one slot for every phone number...")
slots = [None] * 9_999_999_999 # 10 billion slots
slots[9876543210] = "Ravi"
Output:
one slot for every phone number...
Traceback (most recent call last):
File "main.py", line 2, in <module>
slots = [None] * 9_999_999_999 # 10 billion slots
~~~~~~~^~~~~~~~~~~~~~~
MemoryError
Ten billion 8-byte slots is about 80 GB, for a million customers: almost every slot would be empty. We want the instant jump of an index, with only a few slots.
Hashing
Real-life picture: a hostel mail office.
| Mail office | Hash table | In code |
|---|---|---|
| 10 pigeonholes, 0 to 9, not one per room | buckets | a small array |
| Rule: the last digit of the room number (204 → hole 4) | hash function | hash(key) % size |
| Rooms 204 and 314 both land in hole 4 | collision | two keys, one bucket |
| Look through the few letters in that hole | chaining | a small list per bucket |
A hash function turns a key into a number; taking it modulo the number of buckets (% size) gives the bucket index. The same key always lands in the same bucket, so anyone can walk straight to it. A hash table is an array of buckets plus a hash function. A collision is when two different keys land in the same bucket; with chaining, each bucket holds a small list of (key, value) pairs.
def bucket_of(phone, size=10):
return phone % size # last digit -> shelf number
for phone in [9876543210, 9123456785, 9988776650]:
print(phone, "-> shelf", bucket_of(phone))
Output:
9876543210 -> shelf 0
9123456785 -> shelf 5
9988776650 -> shelf 0
Two phones collide on shelf 0. Real hash functions mix all the bits of the key so keys spread evenly, but collisions can always happen, so a hash table must handle them.
Our own HashMap
class HashMap:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
b = self._bucket(key)
for pair in b:
if pair[0] == key: # key already there: update
pair[1] = value
return
b.append([key, value]) # collision? share the bucket
def get(self, key):
for k, v in self._bucket(key):
if k == key:
return v
raise KeyError(key)
phones = HashMap()
phones.put(9876543210, "Ravi")
phones.put(9123456785, "Asha")
phones.put(9988776650, "Neha")
phones.put(9876543210, "Ravi Kumar")
print(phones.get(9876543210), "|", phones.get(9988776650))
print([len(b) for b in phones.buckets])
print(phones.get(9000000000))
Output:
Ravi Kumar | Neha
[0, 1, 2, 0, 0, 0, 0, 0]
Traceback (most recent call last):
File "main.py", line 26, in <module>
print(phones.get(9000000000))
~~~~~~~~~~^^^^^^^^^^^^
File "main.py", line 17, in get
raise KeyError(key)
KeyError: 9000000000
Note [[] for _ in range(size)], not [[]] * size: the second makes one list shared by every bucket. get only looks in one small bucket instead of a million customers, so as long as buckets stay small, put and get are O(1) on average.
Keeping buckets small: load factor and resizing
- Load factor = number of items ÷ number of buckets.
- When it gets too high (for example above 0.75), make twice as many buckets and re-insert (rehash) every item, because
hash(key) % sizechanges whensizechanges. - That copy is O(n) but rare, so
putstays O(1) amortized, the same idea aslist.append. - Worst case: if every key collided, one bucket would hold everything and lookups would be O(n). Good hash functions make this very unlikely.
Python's dict uses a variant called open addressing (a colliding key tries other slots in the same array instead of a list), keeps the load factor low, and since Python 3.7 also remembers insertion order. set is the same idea with keys only.
hash() and hashable keys
print(hash(42), hash(9876543210))
print(hash("chai") == hash("chai"))
print(hash((12, 5)))
table = {}
table[(12, 5)] = "seat booked" # a tuple key: fine
print(table)
table[[12, 5]] = "seat booked" # a list key?
Output:
42 9876543210
True
-9076890671371252903
{(12, 5): 'seat booked'}
Traceback (most recent call last):
File "main.py", line 7, in <module>
table[[12, 5]] = "seat booked" # a list key?
~~~~~^^^^^^^^^
TypeError: unhashable type: 'list'
- Small integers hash to themselves.
- The same string gives the same hash during one run, but string hashes are randomised between runs (for security, against attackers who pick colliding keys), so never save them to a file.
- A hashable object has a hash that never changes during its life. Immutable built-ins are hashable:
int,float,str,tuple(of hashable items),frozenset. Mutable ones are not:list,dict,set. - Why: if a list key changed after being stored, its hash would change and it would sit in the wrong bucket forever. So dict keys and set items must be hashable. Use a tuple like
(12, 5)for a multi-part key. - Your own classes are hashable by identity by default; if you define
__eq__, define__hash__too (or use@dataclass(frozen=True), episode 27).
The payoff: list vs set vs dict
import timeit
phones = list(range(1_000_000))
phone_set = set(phones)
phone_book = {p: "customer" for p in phones}
last = 999_999
print(f"list: {timeit.timeit(lambda: last in phones, number=100):.6f} s")
print(f"set: {timeit.timeit(lambda: last in phone_set, number=100):.6f} s")
print(f"dict: {timeit.timeit(lambda: phone_book[last], number=100):.6f} s")
Output (one run):
list: 0.462035 s
set: 0.000008 s
dict: 0.000010 s
Tens of thousands of times faster: O(n) vs O(1).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
orders[0] on a LinkedList |
TypeError: 'LinkedList' object is not subscriptable |
no numbered slots | walk from head |
| a fixed-count walk | AttributeError: 'NoneType' object has no attribute 'value' |
walked past the end | while node is not None |
head = head.next to walk |
the list is gone | head is the only way in | walk with a separate variable |
slots = [None] * 9_999_999_999 |
MemoryError |
one slot per possible key | hash into a few buckets |
table[[12, 5]] = ... |
TypeError: unhashable type: 'list' |
lists can change | use a tuple (12, 5) |
[[]] * 8 for buckets |
every key lands in every bucket | one list, shared 8 times | [[] for _ in range(8)] |
my_map.get(key) for a missing key in our class |
KeyError: ... |
the key isn't there | return a default, like dict.get |
Mini project: Raju's phone book, from scratch
- A
HashMapwith 8 buckets:put,get(with a default),delete. - Count the items; when
count / buckets > 0.75, double the buckets and re-insert. - Store 1,000 customers (phone → name).
- Print the longest bucket: it should stay small.
- Keep recent VIP calls in a linked list, newest at the front.
- Check every answer against a real
dict.
Solution
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
class HashMap:
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
self.count = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)]
def put(self, key, value):
b = self._bucket(key)
for pair in b:
if pair[0] == key:
pair[1] = value
return
b.append([key, value])
self.count += 1
if self.count / len(self.buckets) > 0.75: # load factor
self._resize()
def get(self, key, default=None):
for k, v in self._bucket(key):
if k == key:
return v
return default
def delete(self, key):
b = self._bucket(key)
for i, (k, _) in enumerate(b):
if k == key:
b.pop(i)
self.count -= 1
return True
return False
def _resize(self):
old = self.buckets
self.buckets = [[] for _ in range(len(old) * 2)]
for bucket in old:
for k, v in bucket:
self.buckets[hash(k) % len(self.buckets)].append([k, v])
book, real = HashMap(), {}
for i in range(1000):
phone, name = 9_000_000_000 + i * 7919, f"customer {i}"
book.put(phone, name)
real[phone] = name
book.delete(9_000_000_000)
del real[9_000_000_000]
same = all(book.get(p) == n for p, n in real.items())
print("items:", book.count, "| buckets:", len(book.buckets), "| same as dict:", same)
print("longest bucket:", max(len(b) for b in book.buckets))
print(book.get(9_000_007_919), "|", book.get(1234, "not found"))
vip = None # linked list, newest first
for phone in [9_000_007_919, 9_000_015_838, 9_000_023_757]:
vip = Node(phone, vip)
node = vip
while node:
print("VIP call:", book.get(node.value))
node = node.next
Output:
items: 999 | buckets: 2048 | same as dict: True
longest bucket: 1
customer 1 | not found
VIP call: customer 3
VIP call: customer 2
VIP call: customer 1
Practice
1. Add push_back in O(1) with a tail pointer.
Solution
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
class LinkedList:
def __init__(self):
self.head = self.tail = None
def push_back(self, value): # O(1) with a tail pointer
node = Node(value)
if self.tail is None:
self.head = self.tail = node
else:
self.tail.next = node
self.tail = node
def __str__(self):
parts, node = [], self.head
while node:
parts.append(str(node.value)); node = node.next
return " -> ".join(parts) + " -> None"
ll = LinkedList()
for x in ["chai", "samosa", "toast"]:
ll.push_back(x)
print(ll)
Output: chai -> samosa -> toast -> None
2. Reverse a linked list in place (a top interview question).
Solution
class Node:
def __init__(self, value, next=None):
self.value, self.next = value, next
def reverse(head):
prev = None
while head:
nxt = head.next # save the rest
head.next = prev # flip the arrow
prev, head = head, nxt
return prev
head = Node(1, Node(2, Node(3)))
head = reverse(head)
while head:
print(head.value, end=" ")
head = head.next
print()
Output: 3 2 1. One walk, O(n) time, O(1) extra memory.
3. Count words with a hash table.
Solution
text = "chai samosa chai toast chai samosa"
counts = {}
for word in text.split():
counts[word] = counts.get(word, 0) + 1
print(counts)
Output: {'chai': 3, 'samosa': 2, 'toast': 1} (collections.Counter does the same, episode 33).
4. Which of these can be dict keys? 5, "chai", (1, 2), [1, 2], {1, 2}, frozenset({1, 2})
Answer
5, "chai", (1, 2) and frozenset({1, 2}) are hashable. [1, 2] and {1, 2} are mutable, so TypeError: unhashable type.
Quick quiz
class Node:
def __init__(self, v, next=None):
self.v, self.next = v, next
head = Node(1, Node(2, Node(3)))
head = Node(0, head)
print(head.next.next.v)
Options: 0, 1, 2, 3
Answer
2. The list is 1 → 2 → 3; pushing 0 at the front gives 0 → 1 → 2 → 3. head is 0, head.next is 1, head.next.next is 2.
Interview questions
- Array vs linked list? Arrays give O(1) indexing but O(n) insert/delete at the front; linked lists give O(1) insert/delete at a known position but O(n) indexing and extra memory per node.
- How do you detect a cycle in a linked list? Floyd's algorithm: a slow pointer moves 1 step, a fast pointer 2 steps; if they ever meet, there's a cycle. O(n) time, O(1) memory. (Or store visited nodes in a set: O(n) memory.)
- How do you find the middle node in one pass? Slow and fast pointers: when fast reaches the end, slow is in the middle.
- How does a hash table give O(1) lookups? A hash function maps the key to a bucket index; only that bucket is checked. Keeping the load factor low keeps buckets small.
- What is a collision and how is it handled? Two keys mapping to the same bucket. Chaining stores a list per bucket; open addressing probes other slots (Python's dict).
- Why must dict keys be immutable? The bucket is chosen from the hash; if the key changed, its hash would change and it could never be found again.
- What is the worst-case lookup time of a hash table? O(n), when all keys collide. Average is O(1).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Node | A small object holding a value and a link to the next node | Node("chai") |
| Linked list | A chain of nodes joined by next links |
chai -> samosa -> None |
| Reference | A value that points to an object (an arrow) | node.next |
| head | The first node; the only way into the list | self.head |
| tail | The last node, kept for O(1) push_back |
self.tail |
None (at the end) |
The last node's next: nothing after it |
node.next is None |
| Walk / traversal | Visiting nodes one by one by following next |
while node: node = node.next |
| push_front | Add a node before the head, O(1) | head = Node(x, head) |
| Relink | Change a next to skip over a node |
node.next = node.next.next |
| Garbage collector | Frees objects nothing refers to any more | the removed node |
| Subscriptable | Supports [ ] indexing |
lists yes, our LinkedList no |
| Doubly linked list | Nodes with both prev and next |
collections.deque (blocks) |
MemoryError |
Raised when Python can't get enough memory | 10 billion slots |
| Hashing | Turning a key into a small number to pick a slot | phone % 10 |
| Hash function | A rule that turns a key into a number, same key → same number | hash("chai") |
| Bucket | One slot of a hash table's array | shelf 0 to 7 |
| Hash table / hash map | An array of buckets plus a hash function | dict, our HashMap |
| Collision | Two different keys landing in the same bucket | 9876543210 and 9988776650 |
| Chaining | Handling collisions with a small list per bucket | b.append([key, value]) |
| Open addressing | Handling collisions by trying other slots in the array | Python's dict |
| Load factor | Items ÷ buckets; too high → resize | 0.75 |
| Resize / rehash | Make more buckets and re-insert every item | double from 8 to 16 |
| Hashable | Has a hash that never changes; can be a dict key | int, str, tuple |
| Unhashable | Mutable, so it can't be a dict key or set item | list, dict, set |
KeyError |
Raised when a key isn't in a dict | phones.get(9000000000) |
Summary
- A linked list is nodes joined by
nextlinks, entered throughheadand ending atNone. Adding or removing at the front is O(1); indexing and finding are O(n) walks. - Walk with
while node is not None; remove by relinking around a node. - Hashing turns a key into a bucket index with a hash function. Collisions share a bucket (chaining); resizing keeps the load factor low, so lookups are O(1) on average.
- That's why
dictandsetare fast, and why their keys must be hashable (immutable). - Next episode: trees and graphs, when a node has many links, explored with BFS and DFS.