Listes chaînées

Insérer une valeur en tête d'un tableau d'un million d'éléments demande de décaler un million de cases. L'opération est simple, correcte, et coûte $O(n)$ — refaite dans une boucle, elle donne un algorithme quadratique là où l'on attendait du linéaire.

La même insertion dans une liste chaînée coûte trois affectations, quelle que soit la taille de la liste.

C'est le premier chapitre du semestre où l'on ne conçoit plus un algorithme mais où l'on choisit une structure. Le tableau d'Algorithmique 1 n'était pas un mauvais choix : c'était le seul disponible. À partir d'ici, chaque structure se juge sur le profil des opérations qu'on va lui demander.

La cellule et le chaînage

Une liste chaînée est faite de cellules dispersées en mémoire, chacune contenant une valeur et l'adresse de la suivante.

1tête2 │3 ▼4┌────┬───┐   ┌────┬───┐   ┌────┬───┐   ┌────┬─────┐5│ 12 │ ●─┼──►│  7 │ ●─┼──►│ 43 │ ●─┼──►│  5 │ nul │6└────┴───┘   └────┴───┘   └────┴───┘   └────┴─────┘

Deux différences essentielles avec le tableau, et tout en découle.

Les cellules ne sont pas contiguës. Chacune est allouée séparément, n'importe où en mémoire ; seul le chaînage les relie. On ne peut donc pas calculer l'adresse du $i$-ième élément — il faut suivre les liens depuis la tête.

La taille n'est pas fixée. Ajouter un élément, c'est allouer une cellule ; en retirer un, c'est libérer la sienne. Aucun redimensionnement, aucune recopie.

Un point mérite d'être souligné, parce qu'il relie ce chapitre au bloc I : une liste est un objet récursif. Une liste est vide, ou bien une cellule suivie d'une liste. Toutes ses opérations s'écrivent donc naturellement de deux façons, itérative et récursive — et la version récursive coûte $O(n)$ de pile, ce qui la disqualifie sur les longues listes.

Le coût des opérations

Voici le tableau que le chapitre doit installer. Chaque ligne se justifie par le schéma ci-dessus.

L'insertion en tête tient en deux lignes, et il faut les écrire dans cet ordre :

1nouvelle.suivant ← tête        ← d'abord raccrocher la suite2tête ← nouvelle                ← puis déplacer la tête

Inverser les deux lignes perd toute la liste : tête pointerait sur la nouvelle cellule, dont le champ suivant pointerait sur… elle-même ou sur rien, et les anciennes cellules deviendraient inatteignables. C'est la faute la plus fréquente du chapitre, et le remède est toujours le même : dessiner les flèches avant d'écrire le code.

Deux lignes du tableau méritent un commentaire.

Suppression « si l'on a la précédente ». Retirer une cellule demande de modifier le champ suivant de celle qui la précède. Or dans une liste simplement chaînée, on ne peut pas remonter : disposer de la cellule à supprimer ne suffit pas, il faut avoir gardé la précédente pendant le parcours. C'est ce qui justifie la liste doublement chaînée.

Mémoire par élément. Un pointeur coûte 8 octets sur une machine 64 bits. Une liste d'entiers de 4 octets consomme donc trois fois la mémoire du tableau équivalent, alignement compris. Ce n'est pas un détail sur de gros volumes.

Listes contre tableaux : la vraie réponse

Le tableau de complexités suggère un partage net. La pratique le corrige, et c'est un des points où l'analyse asymptotique seule induit en erreur.

Le chapitre 7 d'architecture a montré pourquoi. Un tableau est contigu : le parcourir exploite parfaitement la localité spatiale, une ligne de cache rapportant seize entiers d'un coup. Les cellules d'une liste sont dispersées : chaque saut est potentiellement un défaut de cache, soit des dizaines de cycles perdus.

Le résultat est contre-intuitif et solidement mesuré : pour parcourir, chercher ou même insérer au milieu, un tableau bat souvent une liste, y compris quand la complexité annonce le contraire. Le décalage de mémoire d'un tableau est une opération séquentielle que le processeur exécute très vite ; la traversée d'une liste pour trouver le point d'insertion est une suite d'accès aléatoires.

La liste garde trois territoires où elle est indiscutable. Quand on insère et supprime beaucoup à des positions déjà connues — sans avoir à les chercher. Quand les éléments sont gros, car les déplacer coûte alors cher et le pointeur devient négligeable. Et quand les éléments doivent être partagés entre plusieurs structures sans être copiés.

La conclusion à retenir n'est pas « la liste est dépassée », c'est : la complexité asymptotique départage les ordres de grandeur, pas les constantes — et sur les petites et moyennes tailles, ce sont les constantes qui décident.

Doublement chaînée, circulaire, avec sentinelle

Trois variantes répondent chacune à une gêne précise.

La liste doublement chaînée ajoute à chaque cellule un pointeur vers la précédente. On peut alors parcourir dans les deux sens et surtout supprimer une cellule connue en $O(1)$. Le prix : un pointeur de plus par cellule, et deux fois plus de liens à maintenir — chaque insertion et chaque suppression met à jour quatre champs au lieu de deux, ce qui multiplie les occasions de se tromper.

La liste circulaire fait pointer la dernière cellule sur la première. Il n'y a plus de fin, seulement un point d'entrée. C'est la structure des files d'attente cycliques et de l'ordonnancement en tourniquet du cours de systèmes : le parcours revient naturellement au premier après le dernier, sans test de fin.

La sentinelle est la plus utile en pratique et la moins connue des étudiants. On ajoute une cellule bidon en tête, qui ne contient aucune donnée et qu'on ne supprime jamais. Son intérêt est de supprimer tous les cas particuliers : la liste n'est jamais vide, il existe toujours une cellule précédente, et l'insertion en tête devient une insertion ordinaire au milieu. Le code perd ses si liste est vide et ses si c'est le premier élément — soit l'essentiel de ses bogues.

Ce qu'une liste rend possible

Deux usages, qui annoncent la suite du semestre.

Une liste est le support naturel d'une pile et d'une file : c'est le chapitre suivant, et l'implémentation y tient en quelques lignes puisque toutes les opérations portent sur les extrémités.

Et le chaînage se généralise. Une cellule qui porte deux pointeurs au lieu d'un n'est plus une liste mais un arbre binaire — c'est le chapitre 7. Une cellule qui en porte un nombre quelconque donne un graphe, au chapitre 9. Les trois blocs qui restent ne font que faire varier le nombre de flèches sortantes.

À vous

L'exercice construit une liste chaînée complète, puis attaque l'exercice d'entretien classique : inverser une liste, d'abord récursivement, ensuite itérativement avec trois pointeurs. Le second est difficile la première fois, et il est formateur pour une raison précise — il ne se résout pas en réfléchissant au code, il se résout en dessinant les trois flèches et en se demandant laquelle déplacer d'abord.

Le squelette contient une insertion en tête dont les deux lignes sont dans le mauvais ordre, et le test le fera voir immédiatement : la liste ne contiendra plus qu'un élément.

// Une cellule : une valeur, un lien. Rien d'autre.
const cellule = (valeur, suivant = null) => ({ valeur, suivant });

function creerListe() {
  return { tete: null, taille: 0 };
}

// ── Insertion en tête ─────────────────────────────────────────────────────
function insererEnTete(L, valeur) {
  const n = cellule(valeur);
  // ← ces deux lignes sont dans le MAUVAIS ordre : la liste sera perdue
  L.tete = n;
  n.suivant = L.tete;
  L.taille++;
  return L;
}

function versTexte(L) {
  const bouts = [];
  let c = L.tete, garde = 0;
  while (c !== null && garde++ < 50) { bouts.push(c.valeur); c = c.suivant; }
  return (bouts.length ? bouts.join(" -> ") : "(vide)") + " -> nul";
}

// ── Suppression de la première occurrence ─────────────────────────────────
function supprimer(L, valeur) {
  let precedente = null, c = L.tete;
  while (c !== null && c.valeur !== valeur) { precedente = c; c = c.suivant; }
  if (c === null) return false;
  // ← à écrire : décrocher c, en distinguant le cas où c est la tête
  L.taille--;
  return true;
}

// ── Inversion récursive ───────────────────────────────────────────────────
// Une liste est vide, ou une cellule suivie d'une liste : l'inversion
// s'écrit donc récursivement, au prix de O(n) de pile.
function inverserRec(c) {
  if (c === null || c.suivant === null) return c;
  const nouvelleTete = inverserRec(c.suivant);
  c.suivant.suivant = c;   // la suivante pointe désormais sur moi
  c.suivant = null;        // et moi sur rien : je deviens la dernière
  return nouvelleTete;
}

// ── Inversion itérative, trois pointeurs ──────────────────────────────────
function inverserIter(L, tracer) {
  let precedente = null, courante = L.tete;
  while (courante !== null) {
    // ← à écrire. Dessinez d'abord : precedente <- courante  suivante
    //   Quelle flèche déplacer en premier sans perdre la suite ?
    break;
  }
  L.tete = precedente;
  return L;
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Remettez insererEnTete dans le bon ordre.
// 2. Écrivez supprimer, sans oublier le cas où la cellule est la tête.
// 3. Écrivez inverserIter, et faites afficher l'état à chaque tour.

const L = creerListe();
for (const v of [5, 43, 7, 12]) insererEnTete(L, v);
console.log("liste :", versTexte(L), "| taille", L.taille);

const cellule = (valeur, suivant = null) => ({ valeur, suivant });
function creerListe() { return { tete: null, taille: 0 }; }

function insererEnTete(L, valeur) {
  const n = cellule(valeur);
  // D'ABORD raccrocher la suite, ENSUITE déplacer la tête. Dans l'autre
  // ordre, l'ancienne liste devient inatteignable.
  n.suivant = L.tete;
  L.tete = n;
  L.taille++;
  return L;
}

function versTexte(L) {
  const bouts = [];
  let c = L.tete, garde = 0;
  while (c !== null && garde++ < 50) { bouts.push(c.valeur); c = c.suivant; }
  return (bouts.length ? bouts.join(" -> ") : "(vide)") + " -> nul";
}

function supprimer(L, valeur) {
  let precedente = null, c = L.tete;
  while (c !== null && c.valeur !== valeur) { precedente = c; c = c.suivant; }
  if (c === null) return false;
  // Deux cas, et c'est exactement ce qu'une sentinelle ferait disparaître.
  if (precedente === null) L.tete = c.suivant;   // c'était la tête
  else precedente.suivant = c.suivant;            // cas général
  L.taille--;
  return true;
}

function inverserRec(c) {
  if (c === null || c.suivant === null) return c;
  const nouvelleTete = inverserRec(c.suivant);
  c.suivant.suivant = c;
  c.suivant = null;
  return nouvelleTete;
}

function inverserIter(L, tracer) {
  let precedente = null, courante = L.tete;
  while (courante !== null) {
    // L'ordre est imposé par une contrainte : dès qu'on écrit dans
    // courante.suivant, la suite est perdue. On la SAUVE donc d'abord.
    const suivante = courante.suivant;   // 1. sauver la suite
    courante.suivant = precedente;       // 2. retourner la flèche
    precedente = courante;               // 3. avancer les deux repères
    courante = suivante;
    if (tracer) {
      console.log("   inversé jusqu'ici : " +
        versTexte({ tete: precedente }) + "   reste : " + versTexte({ tete: courante }));
    }
  }
  L.tete = precedente;
  return L;
}

const L = creerListe();
for (const v of [5, 43, 7, 12]) insererEnTete(L, v);
console.log("liste       :", versTexte(L), "| taille", L.taille);

console.log("supprimer 7 :", supprimer(L, 7), "->", versTexte(L));
console.log("supprimer 12:", supprimer(L, 12), "->", versTexte(L), " (c'était la tête)");
console.log("supprimer 99:", supprimer(L, 99), "->", versTexte(L), " (absente)");

console.log("");
console.log("— inversion itérative, pas à pas —");
const M = creerListe();
for (const v of [4, 3, 2, 1]) insererEnTete(M, v);
console.log("   départ : " + versTexte(M));
inverserIter(M, true);
console.log("   arrivée : " + versTexte(M));

console.log("");
const N = creerListe();
for (const v of [4, 3, 2, 1]) insererEnTete(N, v);
N.tete = inverserRec(N.tete);
console.log("inversion récursive :", versTexte(N), " (O(n) de pile, contre O(1))");

// Les deux inversions font le même travail. La récursive est plus courte à
// écrire et consomme un cadre par élément : sur une liste d'un million de
// cellules, elle fait déborder la pile. L'itérative tient dans trois
// variables — et c'est le cas typique où l'itération l'emporte, la liste
// étant un objet récursif mais de profondeur LINÉAIRE (chapitre 1).

En travaux pratiques

typedef struct Maillon { int valeur; struct Maillon *suivant; } Maillon;

Maillon *inserer_tete(Maillon *tete, int v) {
  Maillon *m = malloc(sizeof *m);
  if (!m) return NULL;             /* le retour est TESTÉ */
  m->valeur = v;
  m->suivant = tete;
  return m;                        /* la nouvelle tête */
}

void liberer(Maillon *tete) {
  while (tete) {
      Maillon *suivant = tete->suivant;   /* AVANT le free */
      free(tete);
      tete = suivant;
  }
}

/* version classique : trois cas */
if (!*tete) return;
if ((*tete)->valeur == v) { Maillon *m = *tete; *tete = m->suivant;
                          free(m); return; }
Maillon *p = *tete;
while (p->suivant && p->suivant->valeur != v) p = p->suivant;
if (p->suivant) { Maillon *m = p->suivant; p->suivant = m->suivant; free(m); }

/* version double pointeur : AUCUN cas particulier */
void supprimer(Maillon **p, int v) {
  while (*p) {
      if ((*p)->valeur == v) {
          Maillon *m = *p;
          *p = m->suivant;
          free(m);
          return;
      }
      p = &(*p)->suivant;
  }
}

Maillon *inverser(Maillon *tete) {
  Maillon *precedent = NULL;
  while (tete) {
      Maillon *suivant = tete->suivant;   /* sauvegarder */
      tete->suivant = precedent;          /* retourner */
      precedent = tete;                   /* avancer */
      tete = suivant;
  }
  return precedent;
}

int a_un_cycle(Maillon *tete) {
  Maillon *lent = tete, *rapide = tete;
  while (rapide && rapide->suivant) {
      lent = lent->suivant;
      rapide = rapide->suivant->suivant;
      if (lent == rapide) return 1;
  }
  return 0;
}

100 000 éléments        liste       tableau dynamique
insertion en tête       0,004 s     2,8 s      ← décalage de tout
insertion en queue      12,4 s      0,003 s    ← parcours complet
                      (0,004 s avec pointeur de queue)
accès à l'élément n/2   0,9 ms      < 1 ns
parcours complet        0,0031 s    0,0004 s   ← MÊME complexité

tableau : éléments CONTIGUS
une ligne de cache de 64 octets = 16 entiers d'un coup
→ 1 défaut de cache pour 16 éléments

liste : maillons DISPERSÉS dans le tas
chaque maillon est ailleurs, imprévisible pour le préchargeur
→ 1 défaut de cache par élément, et 16 octets par maillon
  dont 8 pour le pointeur

Ce que la suite en fait

Le chapitre 6 pose deux structures qui ne sont que des listes bridées : une pile et une file n'autorisent les opérations qu'aux extrémités, et cette restriction est précisément ce qui les rend utiles — elle garantit un coût constant et donne à la structure une sémantique claire.

Le chapitre 8 du cours de programmation implémentera tout cela en C, la même semaine : la cellule y devient une struct avec un champ pointeur, et l'allocation d'une cellule un appel à malloc. C'est là que le chaînage cesse d'être un schéma au tableau pour devenir des adresses réelles — et que le pointeur pendant guette celui qui libère une cellule avant d'avoir lu son champ suivant.

À retenir