Université de Genève · CUI BSc · Algorithmique & Structures de données

Structures de données

Séminaire 6 · Piles · Files · Deques · Listes chaînées · Tables de hachage
1 / 37

Ordre du jour

  • 1 Structures linéaires
  • Comprendre ce que la pile, la file, le deque et la liste chaînée ont en commun
  • 2 Piles (LIFO)
  • push/pop, vérification des parenthèses/crochets, propriété d'inversion
  • 3 Files & Deques (FIFO)
  • enqueue/dequeue, pourquoi collections.deque est important
  • 4 Listes chaînées
  • Liens entre noeuds, insertion rapide en tête, et différences avec list
  • 5 Tables de hachage
  • Comment la fonction de hachage et les buckets rendent dict et set rapides
  • Question clé
  • O(1) — push/pop de la pile
  • O(1) — enqueue/dequeue de la file
  • O(1) — recherche dans une table de hachage
  • Pourquoi ces structures semblent "instantanées" alors qu'un simple parcours de list est O(n) ?
2 / 37

Deux mondes : structures linéaires vs. structures associatives

  • 1. Structures linéaires (basées sur une séquence)
  • Les éléments sont disposés en séquence. Ce qui change, c'est où les éléments entrent et sortent :
  • Pile → uniquement au sommet (LIFO)
  • File → entrée à l'arrière, sortie à l'avant (FIFO)
  • Deque → entrée/sortie par les deux extrémités
  • Liste chaînée → séquence de noeuds reliés
  • 2. Structures associatives (basées sur des clés)
  • La table de hachage (Python dict/set) brise la règle linéaire !
  • Les éléments NE sont PAS trouvés par leur position (avant/arrière).
  • À la place, ils sont trouvés instantanément par leur Key (l'élément lui-même).
  • Cela requiert un mécanisme complètement différent en interne.
3 / 37

Qu'est-ce qu'une pile ?

Qu'est-ce qu'une pile ?
4 / 37

Pile — Visualisation de push et pop

Pile — Visualisation de push et pop
LIFO : le dernier élément inséré est toujours le premier retiré
5 / 37

Pile : propriété d'inversion

Pile : propriété d'inversion
6 / 37

ADT de la pile — le contrat

  • ADT = Abstract Data Type : une *spécification* des opérations et de leur signification,
  • sans préciser comment elles sont implémentées. Pensez-y comme un contrat.
  • Toute implémentation qui respecte ces règles EST une pile.
  • push(item) — ajouter l'élément au sommet · O(1)
  • pop() — supprimer et renvoyer l'élément du sommet · O(1)
  • peek() — renvoyer l'élément du sommet sans le supprimer · O(1)
  • is_empty() — True si aucun élément · O(1)
  • size() — nombre d'éléments · O(1)
  • Les cinq opérations sont O(1) — pas de recherche ni de décalage nécessaires.
  • Remarque : il n'y a pas « get item at index 3 » — cela est hors du contrat.
7 / 37

Pile — implémentation Python

Une liste Python satisfait parfaitement l'ADT de la pile (append/pop sont tous deux 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})'
8 / 37

Qu'est-ce qu'une file ?

Qu'est-ce qu'une file ?
9 / 37

File en Python — Pourquoi pas list.pop(0) ?

  • Règle générale : n'utilisez jamais list.pop(0) comme file — utilisez collections.deque.
  • list.pop(0) — O(n) [lent]
  • # 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) [rapide]
  • 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.
10 / 37

File : visualisation FIFO

File : visualisation FIFO
Les éléments entrent par l'arrière et sortent par l'avant, premier entré, premier sorti
11 / 37

File — implémentation Python

Envelopper collections.deque pour faire respecter l'interface ADT de la file :
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
12 / 37

Exemple de file : jeu de la patate chaude — mêmes règles que le séminaire (k−1 rotations, puis éliminer l'avant)

(1) Explication du jeu. Visualisation personnelle suivant (Miller)
(1) Explication du jeu. Visualisation personnelle suivant (Miller)
(2) Une élimination en round-robin. Visualisation personnelle suivant (Miller)
(2) Une élimination en round-robin. Visualisation personnelle suivant (Miller)
13 / 37

Application : simulation du jeu de la patate chaude

  • Même paramètre k que l'exercice 2.4 : à chaque tour, k−1 rotations puis éliminer l'avant.
  • Élimination en round-robin en utilisant une file
  • 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)
  • Motif clé : dequeue depuis l'avant, re-enqueue à l'arrière — round-robin FIFO parfait.
14 / 37

Comparaison — Pile vs File

Comparaison — Pile vs File
15 / 37

Qu'est-ce qu'un deque ?

Qu'est-ce qu'un deque ?
16 / 37

Deque : visualisation des deux extrémités

Deque : visualisation des deux extrémités
Un deque peut ajouter ou supprimer aux deux extrémités en O(1)
17 / 37

Deque : interface ADT

Envelopper collections.deque pour faire respecter l'interface ADT du deque :
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
18 / 37

Application : vérification de palindrome avec un deque

Application : vérification de palindrome avec un deque
19 / 37

Qu'est-ce qu'une liste chaînée ?

Qu'est-ce qu'une liste chaînée ?
20 / 37

Liste chaînée — animation d'insertion en queue

Liste chaînée — animation d'insertion en queue
Traverser jusqu'au dernier noeud, puis faire pointer son 'next' vers le nouveau noeud — O(n)
21 / 37

Liste chaînée — implémentation Python

Classe Node + LinkedList avec prepend en O(1) et append en O(n) :
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def prepend(self, data):      # O(1) — update one reference
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def append(self, data):       # O(n) — traverse to end
        new_node = Node(data)
        if not self.head:
            self.head = new_node; return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node
22 / 37

Liste chaînée — Opérations et complexité

OpérationCoûtPourquoi
prepend (insertion en tête)O(1)Rediriger uniquement la référence head
append (insertion en queue)O(n)Doit parcourir jusqu'au dernier noeud
search(value)O(n)Suivre les références next une par une
delete(value)O(n)Doit d'abord trouver le noeud, puis rediriger les références
access by indexO(n)Pas d'arithmétique d'adresse — il faut parcourir
insert after known nodeO(1)Rediriger deux références ; le noeud est déjà en main
23 / 37

Liste doublement chaînée & deque de Python

  • Une liste simplement chaînée possède une référence par noeud : next uniquement.
  • Une liste doublement chaînée ajoute une référence prev → insertion/suppression O(1) aux deux extrémités.
  • C'est exactement ce que collections.deque est en interne.
  • Utilisé par : cache LRU (Least Recently Used), historique de navigateur, curseur d'éditeur de texte.
  • Compromis : 2× mémoire par noeud par rapport à une liste simplement chaînée, mais O(1) aux deux extrémités.
  • Lorsque vous appelez deque.appendleft() en Python, vous effectuez une insertion de liste doublement chaînée.
24 / 37

collections.deque — O(1) aux deux extrémités

Même structure utilisée pour la file et la vérification de palindrome :
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
25 / 37

Introduction aux tables de hachage

  • Vous avez 1 000 000 de noms dans une liste. 'Alice' y est-elle ?
  • Parcours linéaire : vérifier nom 1, nom 2, ... jusqu'à 1 000 000 → O(n).
  • Un annuaire a des onglets par lettre : allez directement sur 'A' — pas de parcours.
  • Imaginez 26 buckets (un par lettre) : placez chaque nom dans le bucket de sa première lettre.
  • Trouver 'Alice' : allez dans le bucket 'A', parcourez seulement les noms en A → beaucoup plus rapide.
  • Pouvons-nous faire encore mieux — un bucket pour chaque clé possible ?
  • Recherche = calculer l'indice du bucket → y aller → terminé → O(1).
  • C'est l'idée centrale d'une table de hachage.
26 / 37

Table de hachage — comment fonctionne la recherche

Table de hachage — comment fonctionne la recherche
27 / 37

Fonctions de hachage — transformer des clés en indices

Une fonction de hachage renvoie un grand nombre. Le modulo (%) le ramène à un indice de bucket valide :
# 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
28 / 37

Gérer les collisions en Python

  • Une collision survient lorsque deux clés différentes visent le même indice de bucket :
  • hash('cat') % 10 == 4 AND hash('bat') % 10 == 4
  • Deux stratégies courantes : chaînage séparé (le bucket contient une courte liste d'entrées) vs adressage ouvert (si le bucket d'origine est occupé, sonder pour un autre indice de bucket).
  • Dans ce séminaire, le modèle par chaînage est SimpleHashMap : chain = self._buckets[idx].
  • Les dict / set de CPython utilisent l'adressage ouvert (sondage, pas de chaînage par bucket).
  • Si les sondages ou les chaînes s'allongent, pourquoi la recherche reste-t-elle en moyenne O(1) ?
  • Python maintient le facteur de charge bas et redimensionne avant que les collisions ne dominent.
29 / 37

Table de hachage : visualisation du chaînage

Table de hachage : visualisation du chaînage
Si deux clés atterrissent dans un bucket, conservez-les toutes deux dans une courte chaîne
30 / 37

dict et set Python — tables de hachage sous le capot

  • Chaque dict et set Python est une table de hachage.
  • La recherche commence par hash(key) ; les collisions sont résolues par adressage ouvert (sondage pour un autre indice de bucket) — pas en parcourant une chaîne comme notre GIF SimpleHashMap.
  • 'key' in my_set suit la même logique ; la présence reste en moyenne O(1).
  • Facteur de charge : lorsque la table est >66% pleine, Python double le tableau et recalcule les hachages.
  • Cela maintient les sondages courts → O(1) moyen maintenu.
  • Pourquoi ne pouvez-vous pas utiliser une list comme clé de dict ?
  • Les listes sont mutables — leur hash changerait après modification.
  • Python n'autorise que des clés hashable (immutables) : str, int, tuple, frozenset.
  • dict stocke des paires (key, value) ; set ne stocke que des clés — les deux donnent une recherche O(1).
31 / 37

Structures principales en un coup d'œil

StructureRègle d'accèsAjouterSupprimerIntégré (Python)
Tableau (list)Accès par indexajouter en finpop/removelist
Liste chaînéeParcours séquentielO(1) en têteO(n) recherche + unlink(classe Node manuelle)
PileLIFOpush → sommetpop ← sommetlist (append/pop)
FileFIFOenqueue → arrièredequeue ← avantcollections.deque
DequeLes deux extrémitésappendleft / appendpopleft / popcollections.deque
32 / 37

Résumé de complexité — les cinq structures

StructureAccès par indexRechercheInsertionSuppression
Tableau (list)O(1)O(n)O(n)*O(n)
Liste chaînéeO(n)O(n)O(1)†O(1)†
Pile——O(1)O(1)
File (deque)——O(1)O(1)
Table de hachage—O(1)*O(1)*O(1)*

* Cas moyen : table de hachage O(1) suppose une bonne fonction de hachage et un facteur de charge faible ; pire cas O(n) en cas de nombreuses collisions. L'insertion dans un tableau à un index arbitraire est O(n) ; append en fin est amorti O(1).

† Liste chaînée : insertion/suppression O(1) quand vous avez une référence au noeud ou agissez sur une extrémité ; trouver la position est O(n).

33 / 37

Choisir la bonne structure

Choisir la bonne structure
34 / 37

Exercices du jour

  • 2.1 — Listes : fusionner deux listes triées en temps linéaire (deux indices ; pas de triche sorted(a+b))
  • 2.2 — Liste chaînée : inverser une liste — approche simple utilise to_list + prepend, ou pointeurs prev/cur/nxt
  • 2.3 — Pile : vérificateur d'équilibrage de (), [], {} (appariement LIFO)
  • 2.4 — File : patate chaude — faire tourner k−1 fois, éliminer, répéter jusqu'à ce qu'il reste un joueur
  • 2.5 — Table de hachage : fréquences de mots avec SimpleHashMap uniquement (get / put, pas de dict/Counter)
35 / 37

Points clés

CaractéristiquePileFileDequeListe chaînéeTable de hachage
DonnéesLIFO (seulement le sommet)FIFO (avant vers arrière)Les deux extrémitésNoeuds + référence nextClé vers valeur
Idée d'implémentationUtiliser une liste pour push/pop au sommetUtiliser collections.dequeUtiliser collections.dequeStocker la référence head et Node.nextUtiliser buckets et chaînage (dict/set)
Coût d'accèsPeek sommet : O(1), index : O(n)Peek front : O(1)Extrémités : O(1), index : O(n)Accès par index : O(n)Recherche moyenne : O(1)
Coût insertion/suppressionpush/pop au sommet : O(1)enqueue/dequeue aux extrémités : O(1)append/popleft/pop : O(1)insertion en tête : O(1), recherche : O(n)insertion/suppression/recherche moyenne : O(1)
Usages typiquesannulation, pile d'appels, vérification des parenthèsesBFS, ordonnancement, file d'impressionfenêtre glissante, vérification de palindromeinsertion en tête, structures basées sur des référencesmise en cache, tests d'appartenance rapides
Coût mémoireO(n) élémentsO(n) élémentsO(n) élémentsO(n) noeuds + référence par noeudPlus d'espace pour les buckets
Exemples d'opérationspush, pop, peekenqueue, dequeue, peekappendleft, append, popleft, popprepend, append, search, deleteinsert, get, remove
36 / 37
Université de Genève · CUI BSc · Algorithmique & Structures de données

Merci et bon hacking !

Suivant : récursion
37 / 37