University of Geneva · CUI BSc · Algorithmics & Data Structures

Data Structures

Seminar 6 · Stacks · Queues · Deques · Linked Lists · Hash Tables
1 / 38

Today's Agenda

1
Linear Structures
Understand what Stack, Queue, Deque, and Linked List have in common
2
Stacks (LIFO)
push/pop, bracket checking, reversal property
3
Queues & Deques (FIFO)
enqueue/dequeue, why collections.deque matters
4
Linked Lists
Node links, fast insert at head, and how it differs from list
5
Hash Tables
How hash and buckets make dict and set fast
Key Question
O(1)
stack push / pop
O(1)
queue enqueue / dequeue
O(1)
hash table lookup
Why do these structures feel "instant" while a plain list scan is O(n)?
2 / 38

Homework Reading

Week 6 follows chapter 4 in the Book "Problem Solving with Algorithms and Data Structures using Python", so we encourage you to read it as homework.

3 / 38

Two Worlds: Linear vs. Associative Structures

  • 1. Linear Structures (Sequence-based)
  • Items are arranged in a sequence. What differs is where items enter and leave:
  • Stack → only at the top (LIFO)
  • Queue → enter at rear, leave at front (FIFO)
  • Deque → enter/leave at both ends
  • Linked List → sequence of connected nodes
  • 2. Associative Structures (Key-based)
  • The Hash Table (Python dict/set) breaks the linear rule!
  • Items are NOT found by their position (front/back).
  • Instead, they are found instantly by their Key (the item itself).
  • This requires a completely different mechanism under the hood.
4 / 38

What is a Stack?

What is a Stack?
5 / 38

Stack — Push & Pop Visualised

Stack — Push & Pop Visualised
LIFO: the last item pushed is always the first to be popped
6 / 38

Stack: Reversal Property

Stack: Reversal Property
7 / 38

Stack ADT — The Contract

  • ADT = Abstract Data Type: a *specification* of operations and their meaning,
  • without saying how they are implemented. Think of it as a contract.
  • Any implementation that satisfies these rules IS a stack.
  • push(item) — add item to the top · O(1)
  • pop() — remove and return the top item · O(1)
  • peek() — return the top item without removing it · O(1)
  • is_empty() — True if no items · O(1)
  • size() — number of items · O(1)
  • All five operations are O(1) — no searching or shifting needed.
  • Notice: there is no "get item at index 3" — that is outside the contract.
8 / 38

Stack — Python Implementation

A Python list satisfies the Stack ADT perfectly (append/pop are both O(1)):
class Stack:
    def __init__(self):
        self._data = []          # internal list — hidden from caller

    def push(self, item):        # O(1)
        self._data.append(item)

    def pop(self):               # O(1)
        if self.is_empty():
            raise IndexError('Stack underflow')
        return self._data.pop()

    def peek(self):              # O(1) — look without removing
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

    def __repr__(self):
        return f'Stack({self._data})'
9 / 38

What is a Queue?

What is a Queue?
10 / 38

Queue in Python — Why Not list.pop(0)?

Rule of thumb: never use list.pop(0) as a queue — use collections.deque.

list.pop(0) — O(n) [slow]
# Every pop(0) shifts ALL elements left
queue = []
queue.append('A')    # enqueue
queue.append('B')
queue.pop(0)         # O(n) — shifts B

# At n = 1,000,000 items:
# each pop moves 999,999 elements!
collections.deque — O(1) [fast]
from collections import deque
q = deque()
q.append('A')        # enqueue rear
q.append('B')
q.popleft()          # O(1) — no shift

# deque is a doubly-linked list
# internally — O(1) at both ends.
11 / 38

Queue: FIFO Visual

Queue: FIFO Visual
Items enter at the rear and leave from the front, first in first out
12 / 38

Queue — Python Implementation

Wrap collections.deque to enforce the Queue ADT interface:
from collections import deque

class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, item):       # O(1)
        self._data.append(item)

    def dequeue(self):             # O(1)
        if self.is_empty():
            raise IndexError('Queue underflow')
        return self._data.popleft()

    def peek(self):
        return self._data[0]

    def size(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data) == 0
13 / 38

Queue example: hot potato — same rules as the seminar (k−1 rotations, then eliminate front)

(1) The game explained. Own visualization following (Miller)
(1) The game explained. Own visualization following (Miller)
(2) One round-robin elimination. Own visualization following (Miller)
(2) One round-robin elimination. Own visualization following (Miller)
14 / 38

Application: Hot Potato Simulation

Same parameter k as Exercise 2.4: each round, k−1 rotations then eliminate the front.

Round-Robin Elimination Using a Queue
def hot_potato(names, k):
    q = Queue()
    for name in names:
        q.enqueue(name)
    while q.size() > 1:
        for _ in range(k - 1):       # rotate front to rear
            q.enqueue(q.dequeue())
        q.dequeue()                   # eliminate front
    return q.dequeue()

names = ['Bill','David','Susan','Jane','Kent','Brad']
print(hot_potato(names, 8))   # → 'Susan' (same as seminar notebook with this k)

Key pattern: dequeue from front, re-enqueue at rear — perfect FIFO round-robin.

15 / 38

Comparison — Stack vs Queue

Comparison — Stack vs Queue
16 / 38

What is a Deque?

What is a Deque?
17 / 38

Deque: Both Ends Visual

Deque: Both Ends Visual
A deque can add or remove from both ends in O(1)
18 / 38

Deque: ADT interface

Wrap collections.deque to enforce the Deque ADT interface:
from collections import deque

class Deque:
    def __init__(self):
        self._data = deque()

    def add_front(self, item):     # O(1)
        self._data.appendleft(item)

    def add_rear(self, item):      # O(1)
        self._data.append(item)

    def remove_front(self):        # O(1)
        if self.is_empty():
            raise IndexError('Deque underflow')
        return self._data.popleft()

    def remove_rear(self):         # O(1)
        if self.is_empty():
            raise IndexError('Deque underflow')
        return self._data.pop()

    def peek_front(self):
        return self._data[0]

    def peek_rear(self):
        return self._data[-1]

    def size(self):
        return len(self._data)

    def is_empty(self):
        return len(self._data) == 0
19 / 38

Deque Application: Palindrome Checker

Deque Application: Palindrome Checker
20 / 38

What is a Linked List?

What is a Linked List?
21 / 38

Linked List — Insert at Tail Animation

Linked List — Insert at Tail Animation
Traverse to the last node, then reference its 'next' to the new node — O(n)
22 / 38

Linked List - ADT

Core state: references to head (and optionally tail) plus a logical size.

LinkedListADT
  + is_empty() -> bool
  + size() -> int
  + prepend(x: T) -> None        # O(1)
  + append(x: T) -> None         # O(1) with tail, else O(n)
  + remove_front() -> T          # O(1)
  + find(x: T) -> bool           # O(n)
  + insert_after(target, x)      # O(n) to find target

Performance idea: fast updates at known positions, but sequential traversal for search/index access.

Use linked lists when many inserts/deletes happen near ends or around known nodes.

23 / 38

Linked List — Operations & Complexity

OperationCostWhy
prepend (insert at head)O(1)Redirect head reference only
append (insert at tail)O(n)Must traverse to last node
search(value)O(n)Follow next references one by one
delete(value)O(n)Must find node first, then redirect
access by indexO(n)No address arithmetic — must traverse
insert after known nodeO(1)Redirect two references; node already in hand
24 / 38

Doubly Linked List & Python's deque

  • A singly linked list has one reference per node: next only.
  • A doubly linked list adds a prev reference → O(1) insert/delete at both ends.
  • This is exactly what collections.deque is under the hood.
  • Used by: LRU (Least Recently Used) cache, browser history, text-editor cursor.
  • Trade-off: 2× memory per node vs singly linked, but O(1) at both ends.
  • When you call deque.appendleft() in Python, you are calling a doubly linked list insert.
25 / 38

collections.deque — O(1) at Both Ends

Same structure you used for Queue and palindrome checking:
from collections import deque

d = deque([10, 20, 30])
d.appendleft(5)    # insert at front — O(1)
d.append(40)         # insert at rear — O(1)
d.popleft()          # → 5
d.pop()              # → 40
26 / 38

Introduction to Hash Tables

  • You have 1,000,000 names in a list. Is 'Alice' there?
  • Linear scan: check name 1, name 2, ... up to 1,000,000 → O(n).
  • A phonebook has letter tabs: go straight to 'A' — no scanning.
  • Imagine 26 buckets (one per letter): put each name in its first-letter bucket.
  • Find 'Alice': go to bucket 'A', scan only A-names → much faster.
  • Can we do even better — a bucket for every possible key?
  • Lookup = compute bucket index → go there → done → O(1).
  • That is the core idea of a hash table.
27 / 38

Hash Table — How the Lookup Works

Hash Table — How the Lookup Works
28 / 38

Hash Functions — Turning Keys into Indices

A hash function gives a giant number. Modulo (%) forces it into a valid bucket index:
# 1. Get a giant integer using Python's hash()
print(hash('alice'))   # e.g. 4632849283746523

# 2. Our hash table has capacity = 10 buckets (indices 0 to 9).
# How do we fit this giant number into our smaller array?
# Solution: modulo (%) gives the remainder.
capacity = 10
bucket_for_alice = hash('alice') % capacity   # remainder by 10 is 3
bucket_for_bob   = hash('bob') % capacity     # remainder by 10 is 7

# Any huge number % 10 will ALWAYS be in 0..9.
# So, 'alice' goes to bucket 3, 'bob' goes to bucket 7.

# Key properties of a good hash function:
#   Deterministic: same input → always same output
#   Fast to compute: O(1)
#   Spreads values evenly: minimizes collisions
29 / 38

Handling Collisions in Python

  • A collision occurs when two different keys target the same bucket index:
  • hash('cat') % 10 == 4 AND hash('bat') % 10 == 4
  • Two common strategies: separate chaining (bucket holds a short list of entries) vs open addressing (if the home bucket is busy, probe forward for another bucket index).
  • In this seminar, the chaining model is SimpleHashMap: chain = self._buckets[idx].
  • CPython's dict / set use open addressing (probing, not chaining per bucket).
  • If probing or chains grow, why is lookup still O(1) on average?
  • Python keeps the load factor low and resizes before collisions dominate.
30 / 38

Hash Table: Chaining Visual

Hash Table: Chaining Visual
If two keys land in one bucket, keep both in a short chain
31 / 38

Python dict and set — Hash Tables Under the Hood

  • Every Python dict and set is a hash table.
  • Lookup starts from hash(key); collisions are resolved by open addressing (probe for another bucket index) — not by scanning a chain like our SimpleHashMap GIF.
  • 'key' in my_set follows same logic; presence is still average O(1).
  • Load factor: when the table is >66% full, Python doubles the array and rehashes.
  • That keeps probes short → average O(1) maintained.
  • Why can't you use a list as a dict key?
  • Lists are mutable — their hash would change after modification.
  • Python only allows hashable (immutable) keys: str, int, tuple, frozenset.
  • dict stores (key, value) pairs; set stores only keys — both give O(1) lookup.
32 / 38

Core Structures at a Glance

StructureAccess RuleAddRemovePython Built-in
Array (list)Index basedappend at endpop/removelist
Linked ListSequential traversalO(1) at headO(n) find + unlink(manual Node class)
StackLIFOpush → toppop ← toplist (append/pop)
QueueFIFOenqueue → reardequeue ← frontcollections.deque
DequeBoth endsappendleft / appendpopleft / popcollections.deque
33 / 38

Complexity Summary — All Five Structures

StructureAccess by indexSearchInsertDelete
Array (list)O(1)O(n)O(n)*O(n)
Linked ListO(n)O(n)O(1)†O(1)†
Stack——O(1)O(1)
Queue (deque)——O(1)O(1)
Hash Table—O(1)*O(1)*O(1)*

* Average case: hash table O(1) assumes a good hash and load factor; worst case O(n) with many collisions. Array insert at arbitrary index is O(n); append at end is amortized O(1).

† Linked list: O(1) insert/delete when you have a reference to the node or act at an end; finding the position is O(n).

34 / 38

Choosing the Right Structure

Choosing the Right Structure
35 / 38

Today's Exercises

  • 2.1 — Lists: merge two sorted lists in linear time (two indices; no sorted(a+b) cheat)
  • 2.2 — Linked list: reverse a list — easier track uses to_list + prepend, or pointer prev/cur/nxt
  • 2.3 — Stack: balanced (), [], {} checker (LIFO matching)
  • 2.4 — Queue: hot potato — rotate k−1 times, eliminate, repeat until one player remains
  • 2.5 — Hash table: word frequencies with SimpleHashMap only (get / put, no dict/Counter)
36 / 38

Key Takeaways

FeatureStackQueueDequeLinked ListHash Table
DataLIFO (top only)FIFO (front to rear)Both endsNodes + next referenceKey to value
Implementation ideaUse a list for top push/popUse collections.dequeUse collections.dequeStore head reference and Node.nextUse buckets and chaining (dict/set)
Access costPeek top: O(1), index: O(n)Peek front: O(1)Ends: O(1), index: O(n)Index is O(n)Lookup avg: O(1)
Insert/remove costpush/pop at top: O(1)enqueue/dequeue at ends: O(1)append/popleft/pop: O(1)insert at head: O(1), search: O(n)insert/delete/lookup avg: O(1)
Typical usesundo, call stack, bracket checkingBFS, scheduling, print queuesliding window, palindrome checksinsert at head, reference-based structurescaching, fast membership tests
Memory costO(n) itemsO(n) itemsO(n) itemsO(n) nodes + reference per nodeMore space for buckets
Example operationspush, pop, peekenqueue, dequeue, peekappendleft, append, popleft, popprepend, append, search, deleteinsert, get, remove
37 / 38
University of Geneva · CUI BSc · Algorithmics & Data Structures

Thank You & Happy Hacking!

Next: Recursion
38 / 38