Les structures de données

Changer une structure de données dans un programme lent peut produire le même effet qu'une greffe d'organe sur un patient malade. Des types abstraits importants — conteneurs (containers), dictionnaires (dictionaries), files de priorité (priority queues) — possèdent plusieurs implémentations différentes mais fonctionnellement équivalentes. Remplacer l'une par l'autre ne change pas la correction du programme : on substitue une implémentation correcte à une autre. En revanche, chaque implémentation réalise des compromis de temps différents sur les opérations, et la performance globale peut s'améliorer de façon spectaculaire. Comme pour un patient en attente de greffe, il suffit parfois de remplacer une seule pièce pour régler le problème.

Mais mieux vaut naître avec un bon cœur que d'attendre une transplantation. Le bénéfice maximal des bonnes structures vient de la conception du programme autour d'elles dès le départ. Ce chapitre revisite les trois types abstraits fondamentaux — conteneurs, dictionnaires, files de priorité — et montre comment les implémenter avec des tableaux, des listes, des arbres et des tas. Les exemples du livre sont en C ; nous les traduisons en TypeScript idiomatique, avec la complexité annoncée à chaque étape.

Contigu contre chaîné

On classe proprement les structures de données en deux familles, selon qu'elles reposent sur des tableaux ou sur des pointeurs :

• Les structures contiguës (contiguously-allocated) occupent un bloc de mémoire d'un seul tenant : tableaux, matrices, tas, tables de hachage.
• Les structures chaînées (linked) sont des morceaux de mémoire distincts reliés par des pointeurs : listes, arbres, listes d'adjacence de graphes.

Les tableaux

Le tableau (array) est la structure contiguë fondamentale : des enregistrements de taille fixe, chacun localisé efficacement par son index (ou, ce qui revient au même, son adresse). Une bonne analogie est une rue de maisons identiques numérotées de 1 à n : connaissant le numéro, on calcule immédiatement la position exacte de la maison.

Trois avantages découlent de cette disposition :

• Accès en temps constant par l'index — l'index se traduit directement en adresse mémoire, donc on lit n'importe quel élément instantanément.
• Efficacité mémoire — le tableau ne contient que des données, sans pointeur ni information de fin d'enregistrement.
• Localité mémoire — parcourir tous les éléments exploite à merveille la mémoire cache des processeurs modernes, car les accès successifs sont physiquement contigus.

Le défaut du tableau est qu'on ne peut pas ajuster sa taille en cours d'exécution. Le programme échoue dès qu'on insère le (n + 1)-ième élément si l'on n'a alloué de la place que pour n. La parade est le tableau dynamique (dynamic array) : on part d'une taille 1 et on double la capacité de m à 2m à chaque débordement, en recopiant l'ancien contenu dans la moitié basse du nouveau bloc.

Les pointeurs et les listes chaînées

Les pointeurs (pointers) relient les morceaux d'une structure chaînée : un pointeur stocke l'adresse d'un emplacement mémoire. Une liste chaînée (linked list) est faite de nœuds, chacun comportant un ou plusieurs champs de données et un pointeur vers le nœud suivant ; un pointeur de tête donne l'accès à l'ensemble. Dans une liste doublement chaînée (doubly-linked list), chaque nœud pointe aussi vers son prédécesseur, au prix d'un pointeur supplémentaire.

Les trois opérations de base sont la recherche, l'insertion et la suppression. L'insertion en tête est triviale et ne nécessite aucun parcours. La suppression est plus délicate : il faut d'abord trouver le prédécesseur du nœud visé, car c'est son champ next qu'il faut réécrire.

// Liste simplement chaînée. Insertion en tête : O(1).
// Recherche : O(n). Suppression : O(n) (recherche du prédécesseur).
class Node<T> {
  constructor(public item: T, public next: Node<T> | null = null) {}
}

class LinkedList<T> {
  head: Node<T> | null = null;

  insert(x: T): void {            // O(1)
    this.head = new Node(x, this.head);
  }

  search(x: T): Node<T> | null {  // O(n)
    let p = this.head;
    while (p !== null && p.item !== x) p = p.next;
    return p;
  }

  delete(x: T): void {            // O(n)
    if (this.head === null) return;
    if (this.head.item === x) {
      this.head = this.head.next; // suppression de la tête
      return;
    }
    let pred = this.head;         // recherche du prédécesseur
    while (pred.next !== null && pred.next.item !== x) {
      pred = pred.next;
    }
    if (pred.next !== null) pred.next = pred.next.next;
  }
}

Le verdict du compromis

Les listes chaînées l'emportent quand : il n'y a jamais de débordement tant que la mémoire n'est pas pleine ; les insertions et suppressions sont plus simples qu'en tableau ; déplacer des pointeurs coûte moins cher que déplacer de gros enregistrements. Les tableaux l'emportent quand : on veut économiser l'espace des pointeurs ; on a besoin d'accès aléatoire efficace ; on recherche la localité mémoire et la performance du cache.

Piles et files

Un conteneur est une structure qui range et restitue des données indépendamment de leur contenu ; ce qui distingue les conteneurs, c'est l'ordre de restitution. Les deux plus importants dépendent de l'ordre d'insertion.

• La pile (stack) restitue en ordre dernier entré, premier sorti (LIFO, last-in, first-out). Simple et très efficace, c'est le bon conteneur quand l'ordre n'a aucune importance. Ses opérations s'appellent push (empiler) et pop (dépiler). Le LIFO surgit naturellement dans l'exécution des algorithmes récursifs.
• La file (queue) restitue en ordre premier entré, premier sorti (FIFO, first-in, first-out) — la façon la plus équitable de minimiser le temps d'attente maximal. Ses opérations s'appellent enqueue (enfiler) et dequeue (défiler). La file est la structure qui pilote le parcours en largeur (BFS) dans les graphes.

// Pile (LIFO) : push/pop en O(1) amorti via un tableau dynamique.
class Stack<T> {
  private data: T[] = [];
  push(x: T): void { this.data.push(x); }     // O(1) amorti
  pop(): T | undefined { return this.data.pop(); } // O(1)
  isEmpty(): boolean { return this.data.length === 0; }
}

// File (FIFO) : enqueue/dequeue en O(1) via deux indices.
// On évite shift() (O(n)) en avançant un curseur de tête.
class Queue<T> {
  private data: T[] = [];
  private head = 0;

  enqueue(x: T): void { this.data.push(x); }  // O(1) amorti

  dequeue(): T | undefined {                  // O(1)
    if (this.head >= this.data.length) return undefined;
    const x = this.data[this.head++];
    if (this.head > this.data.length / 2) {   // compactage périodique
      this.data = this.data.slice(this.head);
      this.head = 0;
    }
    return x;
  }
}

Piles et files s'implémentent aussi bien avec des tableaux qu'avec des listes ; la vraie question est de savoir si l'on connaît à l'avance une borne supérieure sur la taille du conteneur, ce qui autoriserait un tableau statique.

Dictionnaires

Le dictionnaire donne accès aux données par leur contenu : on y range un élément pour le retrouver plus tard. Ses opérations primaires sont Search(D, k) (renvoyer l'élément de clé k), Insert(D, x) et Delete(D, x). Certaines implémentations supportent aussi Min/Max (ce qui en fait une file de priorité) et Predecessor/Successor (pour itérer en ordre trié).

En raisonnant à ce niveau abstrait, on s'affranchit des détails de représentation. Le grand intérêt du dictionnaire est de révéler les compromis : une représentation donnée rend certaines opérations efficaces au prix d'autres opérations coûteuses.

Opération	Tableau non trié	Tableau trié	Liste simple non triée	Liste double non triée	Liste simple triée	Liste double triée
Search	O(n)	O(log n)	O(n)	O(n)	O(n)	O(n)
Insert	O(1)	O(n)	O(1)	O(1)	O(n)	O(n)
Delete	O(1)	O(n)	O(n)	O(1)	O(n)	O(1)
Successor	O(n)	O(1)	O(n)	O(n)	O(1)	O(1)
Min / Max	O(n)	O(1)	O(n)	O(n)	O(1)	O(1)

Quelques subtilités méritent commentaire. Sur un tableau non trié, la suppression est O(1) parce qu'on recopie le dernier élément dans le trou puis on décrémente n. Le tableau trié rend la recherche logarithmique (dichotomie) mais l'insertion linéaire (il faut décaler). Pour les listes, le tri apporte moins de bénéfice que pour les tableaux : la recherche dichotomique est impossible faute d'accès à l'élément médian. Et la suppression sur liste simplement chaînée reste O(n) à cause du problème du prédécesseur — que la liste doublement chaînée résout en O(1).

Arbres binaires de recherche

Les structures vues jusqu'ici offrent soit la recherche rapide, soit la mise à jour flexible, mais pas les deux. L'arbre binaire de recherche (binary search tree, BST) combine les deux idées : c'est une « liste à deux pointeurs par nœud ». Pour tout nœud étiqueté x, toutes les clés du sous-arbre gauche sont < x et toutes celles du sous-arbre droit sont > x.

Cette propriété détermine de façon unique l'emplacement de chaque clé. La recherche part de la racine et descend à gauche ou à droite selon que la clé cherchée est plus petite ou plus grande. Le minimum est le descendant le plus à gauche, le maximum le plus à droite. Un parcours infixe (in-order traversal) — gauche, nœud, droite — liste les clés en ordre trié.

class TreeNode<T> {
  left: TreeNode<T> | null = null;
  right: TreeNode<T> | null = null;
  constructor(public item: T) {}
}

class BST<T> {
  root: TreeNode<T> | null = null;

  // Toutes ces opérations sont O(h), h = hauteur de l'arbre.
  search(x: T): TreeNode<T> | null {
    let n = this.root;
    while (n !== null && n.item !== x) {
      n = x < n.item ? n.left : n.right;
    }
    return n;
  }

  insert(x: T): void {            // O(h)
    const node = new TreeNode(x);
    if (this.root === null) { this.root = node; return; }
    let n = this.root;
    for (;;) {
      if (x < n.item) {
        if (n.left === null) { n.left = node; return; }
        n = n.left;
      } else {
        if (n.right === null) { n.right = node; return; }
        n = n.right;
      }
    }
  }

  findMin(n = this.root): TreeNode<T> | null { // O(h)
    if (n === null) return null;
    while (n.left !== null) n = n.left;
    return n;
  }

  // Parcours infixe : visite les clés en ordre trié, en O(n).
  inOrder(visit: (x: T) => void, n = this.root): void {
    if (n === null) return;
    this.inOrder(visit, n.left);
    visit(n.item);
    this.inOrder(visit, n.right);
  }
}

La suppression comporte trois cas. Une feuille s'efface en annulant le pointeur du parent. Un nœud à un seul enfant se retire en reliant directement le petit-enfant au parent. Un nœud à deux enfants se résout en le réétiquetant avec la clé de son successeur immédiat (le plus petit du sous-arbre droit), puis en supprimant physiquement ce successeur, qui a au plus un enfant.

Le besoin d'équilibrage

Toutes les opérations du BST coûtent O(h), où h est la hauteur. La meilleure hauteur possible, pour un arbre parfaitement équilibré, est h = log n — excellent. Mais la forme de l'arbre dépend de l'ordre d'insertion, sur lequel on n'a aucun contrôle. Si l'utilisateur insère les clés déjà triées, on obtient un arbre filiforme de hauteur n, dégénéré en liste chaînée.

Les arbres de recherche équilibrés (balanced search trees) règlent ce problème : après chaque insertion ou suppression, ils ajustent légèrement l'arbre — par des rotations (rotations) — pour garantir une hauteur O(log n), donc des opérations en O(log n). Les arbres AVL, rouge-noir (red-black trees) et splay trees appartiennent à cette famille. Du point de vue de la conception, l'essentiel est de savoir qu'ils existent et qu'on peut les utiliser comme des boîtes noires offrant un dictionnaire efficace.

Files de priorité et tas

Beaucoup d'algorithmes traitent les éléments dans un ordre précis — par exemple ordonnancer des tâches selon leur importance. La file de priorité (priority queue) offre plus de souplesse qu'un simple tri, car elle accepte l'arrivée de nouveaux éléments à tout moment : insérer une tâche y coûte bien moins cher que tout retrier à chaque arrivée. Elle supporte Insert(Q, x), Find-Minimum(Q) et Delete-Minimum(Q).

Opération	Tableau non trié	Tableau trié	Arbre équilibré	Tas binaire
Insert	O(1)	O(n)	O(log n)	O(log n)
Find-Minimum	O(1)	O(1)	O(1)	O(1)
Delete-Minimum	O(n)	O(1)	O(log n)	O(log n)

L'astuce du Find-Minimum en O(1) partout est de mémoriser un pointeur vers l'élément minimal, mis à jour à chaque insertion. Le tas binaire (binary heap) offre le meilleur équilibre général. C'est un arbre binaire complet stocké de façon astucieuse dans un tableau : pour le nœud d'indice i (à partir de 1), l'enfant gauche est en 2i, l'enfant droit en 2i + 1, le parent en ⌊i / 2⌋. Aucun pointeur n'est nécessaire.

Un min-tas (min-heap) maintient l'invariant : tout nœud est inférieur ou égal à ses enfants — donc le minimum est à la racine. L'insertion place l'élément en fin de tableau puis le fait remonter (sift-up / percolate-up) tant qu'il est plus petit que son parent. L'extraction du minimum remplace la racine par le dernier élément puis le fait descendre (sift-down / percolate-down) vers son plus petit enfant. Les deux opérations parcourent au plus la hauteur de l'arbre, soit O(log n).

// Min-tas binaire stocké dans un tableau (indices à partir de 0).
// enfants de i : 2i+1 et 2i+2 ; parent de i : (i-1) >> 1.
class MinHeap {
  private h: number[] = [];

  peek(): number | undefined { return this.h[0]; } // O(1)

  insert(x: number): void {        // O(log n)
    this.h.push(x);
    this.siftUp(this.h.length - 1);
  }

  extractMin(): number | undefined { // O(log n)
    const n = this.h.length;
    if (n === 0) return undefined;
    const min = this.h[0];
    const last = this.h.pop()!;
    if (n > 1) { this.h[0] = last; this.siftDown(0); }
    return min;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.h[i] >= this.h[parent]) break;
      [this.h[i], this.h[parent]] = [this.h[parent], this.h[i]];
      i = parent;
    }
  }

  private siftDown(i: number): void {
    const n = this.h.length;
    for (;;) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.h[l] < this.h[smallest]) smallest = l;
      if (r < n && this.h[r] < this.h[smallest]) smallest = r;
      if (smallest === i) break;
      [this.h[i], this.h[smallest]] =
        [this.h[smallest], this.h[i]];
      i = smallest;
    }
  }
}

Le hachage

La table de hachage (hash table) est souvent la meilleure façon concrète de tenir un dictionnaire : elle exploite le fait qu'un accès indexé dans un tableau est en temps constant. Une fonction de hachage (hash function) traduit chaque clé en entier, qui sert d'index. Pour une chaîne, on la lit d'abord comme un grand nombre en base α (la taille de l'alphabet), puis on réduit ce nombre modulo m (la taille de la table) — idéalement m est un grand nombre premier, pour répartir uniformément les valeurs.

La gestion des collisions

Aussi bonne soit-elle, la fonction finira par envoyer deux clés distinctes au même indice : c'est une collision (collision). Deux stratégies dominent.

• Le chaînage (chaining) représente la table comme un tableau de m listes chaînées ; la i-ième liste contient tous les éléments hachant vers i. Recherche, insertion et suppression se ramènent au problème des listes. Si les n clés sont réparties uniformément, chaque liste compte environ n / m éléments — une constante quand m ≈ n.
• L'adressage ouvert (open addressing) range les éléments directement dans le tableau. En cas de collision, on cherche la prochaine case libre (sondage séquentiel). On économise l'espace des pointeurs, mais la suppression devient délicate : retirer un élément peut casser une chaîne d'insertions, rendant des éléments inaccessibles ; il faut alors réinsérer tous les éléments du segment suivant.

// Table de hachage par chaînage. Search/Insert/Delete en O(n/m)
// en moyenne (≈ O(1) si m ≈ n), O(n) dans le pire cas.
class HashTable<V> {
  private buckets: Array<Array<[string, V]>>;
  constructor(private m = 1024) {
    this.buckets = Array.from({ length: m }, () => []);
  }

  private hash(key: string): number {
    let h = 0;
    for (let i = 0; i < key.length; i++) {
      h = (h * 31 + key.charCodeAt(i)) % this.m; // base 31
    }
    return h;
  }

  insert(key: string, value: V): void {
    const b = this.buckets[this.hash(key)];
    const pair = b.find(([k]) => k === key);
    if (pair) pair[1] = value;
    else b.push([key, value]);
  }

  search(key: string): V | undefined {
    const b = this.buckets[this.hash(key)];
    return b.find(([k]) => k === key)?.[1];
  }

  delete(key: string): void {
    const b = this.buckets[this.hash(key)];
    const i = b.findIndex(([k]) => k === key);
    if (i !== -1) b.splice(i, 1);
  }
}

En espérance, le hachage offre Search, Insert et Delete en O(1) (plus exactement O(n / m) pour la recherche) — d'où sa réputation. Le pire cas théorique est mauvais (toutes les clés dans le même seau, O(n)), mais avec une fonction de hachage correcte on peut compter sur un bon comportement en pratique.

War story : choisir la bonne structure change tout

Deux récits du chapitre illustrent le message central. Dans le premier, Skiena découpe un maillage triangulaire (computer graphics) en bandes (strips) pour accélérer le rendu. L'heuristique gloutonne (greedy) retire à chaque étape la plus longue bande restante. L'implémentation naïve qui re-parcourt tous les triangles à chaque retrait est en O(n²) — sans espoir sur un modèle de 20 000 triangles. En stockant les longueurs des bandes dans une file de priorité (couplée à un dictionnaire pour retrouver chaque triangle), le temps d'exécution s'est amélioré de plusieurs ordres de grandeur.

Dans le second récit (« String 'em Up »), il s'agit de tester si des milliers de sous-chaînes d'ADN appartiennent à un dictionnaire. L'étudiant de Skiena passe successivement de l'arbre binaire de recherche (O(k log n)) à la table de hachage (gain d'un facteur log n), puis — en exploitant le fait que des requêtes consécutives ne diffèrent que d'un caractère — à l'arbre des suffixes, enfin à l'arbre des suffixes compressé pour tenir en mémoire linéaire. De « plus de deux jours » sur 4 096 caractères, le programme passe à traiter 65 536 caractères. Plusieurs leçons : isoler l'opération répétée et optimiser la structure qui la supporte ; commencer simple puis profiler ; exploiter la structure des requêtes ; et persévérer.

À retenir

• Contigu contre chaîné. Les tableaux donnent l'accès indexé O(1) et la localité cache, mais une taille rigide (corrigée par le tableau dynamique, O(n) amorti). Les listes offrent l'insertion/suppression O(1) quand on tient le nœud, mais pas d'accès aléatoire.
• Conteneurs. La pile (LIFO, push/pop) sied quand l'ordre est indifférent ; la file (FIFO, enqueue/dequeue) pilote le parcours en largeur. Les deux sont O(1) par opération.
• Dictionnaires. Aucune représentation ne gagne sur tout : un tableau trié excelle en recherche mais pas en mise à jour ; une liste doublement chaînée fait l'inverse. Raisonnez en opérations abstraites.
• Arbres binaires de recherche. Recherche et mise à jour flexibles en O(h) ; mais h peut dégénérer à n. Les arbres équilibrés (AVL, rouge-noir) garantissent O(log n) via des rotations — utilisez-les comme des boîtes noires.
• Files de priorité et tas. Le tas binaire (min-heap) stocké dans un tableau offre insert et extract-min en O(log n), grâce au sift-up et au sift-down. La file de priorité accepte les arrivées au fil de l'eau.
• Hachage. O(1) en moyenne pour search/insert/delete avec une bonne fonction et la gestion des collisions (chaînage ou adressage ouvert). Souvent la meilleure structure concrète pour un dictionnaire.
• Le message central. Changer de structure de données transforme souvent un algorithme lent en algorithme rapide — comme une greffe d'organe. Concevez votre programme autour des bonnes structures dès le départ.