SyntaxPilot
Courses/Python/Lesson 35
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Python · Lesson 35 of 40

DSA 2: linked lists, hashing

queued

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.

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) % size changes when size changes.
  • That copy is O(n) but rare, so put stays O(1) amortized, the same idea as list.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

  1. A HashMap with 8 buckets: put, get (with a default), delete.
  2. Count the items; when count / buckets > 0.75, double the buckets and re-insert.
  3. Store 1,000 customers (phone → name).
  4. Print the longest bucket: it should stay small.
  5. Keep recent VIP calls in a linked list, newest at the front.
  6. 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

  1. 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.
  2. 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.)
  3. How do you find the middle node in one pass? Slow and fast pointers: when fast reaches the end, slow is in the middle.
  4. 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.
  5. 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).
  6. 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.
  7. 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 next links, entered through head and ending at None. 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 dict and set are 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.