Les structures linéaires

Cinq structures, et une seule question posée cinq fois : qu'est-ce que je suis prêt à payer, et pour quoi ? Aucune n'est meilleure que les autres. Chacune achète une opération rapide en en vendant une autre, et savoir laquelle est exactement ce que l'examen demande.

Un seul voisin de chaque côté

Le module précédent s'est terminé sur une distinction qu'il faut avoir en tête avant de commencer, parce qu'elle organise tout ce qui suit. Un type abstrait de données décrit les opérations et ce qu'elles promettent ; une implémentation décrit la structure interne qui les réalise. « Pile » est un TAD ; « pile faite avec un tableau » est une implémentation. Si ce couple est encore flou, il est détaillé en clôture des Les éléments de C++.

Ce module fait le chemin inverse du précédent : il prend les TAD un par un et les construit pour de bon. Et à chaque fois, la même mécanique apparaît — on choisit une des deux dispositions mémoire, et ce choix décide de toutes les complexités d'un coup.

Voici les deux dispositions, énoncées une fois pour toutes. Le tableau range les éléments côte à côte, dans une zone mémoire d'un seul tenant : on connaît l'adresse du premier et la taille de chaque élément, donc on peut calculer l'adresse de n'importe lequel. La liste chaînée disperse les éléments où il y a de la place, et donne à chacun l'adresse du suivant : on ne calcule rien, on suit.

Tout le reste du module découle de cette phrase. Calculer coûte toujours pareil ; suivre coûte proportionnellement à la distance. En sens inverse : insérer au milieu d'une zone d'un seul tenant oblige à décaler tous les suivants, alors que rebrancher deux adresses ne coûte rien. C'est un échange, pas une hiérarchie — et c'est pour ça que les deux existent encore.

Le tableau : contigu, donc indexable

Commençons par la structure la plus simple, et par ce qu'elle a de remarquable : l'accès à n'importe quel élément coûte la même chose, que le tableau contienne dix éléments ou dix millions.

En mémoire, le calcul est exactement celui-là : l'adresse de tableau[i] vaut l'adresse de tableau[0], plus i fois la taille d'un élément. Une multiplication, une addition, et c'est fini — le même travail quel que soit i. C'est du Θ(1), et c'est le seul endroit de tout le cours où on obtient un accès direct sans rien payer d'autre.

Reste que la vraie vie demande des tableaux qui grandissent. On distingue donc le tableau statique, dont la taille est fixée une fois pour toutes à l'écriture du programme, et le tableau dynamique, alloué dans le tas et capable de s'agrandir. C'est le second qui nous intéresse, et il oblige à tenir deux nombres au lieu d'un.

Le code ci-dessous existe pour une seule raison : montrer où se produit l'agrandissement et ce qu'il coûte. Le reste de la classe est banal — regarde la méthode agrandir et la première ligne d'ajouter, tout est là.

template<typename T>
class Tableau {
private:
    T*  donnees;
    int taille;        // cases OCCUPÉES
    int capacite;      // cases ALLOUÉES

    void agrandir() {                       // coûte O(n) : on recopie tout
        capacite *= 2;                      // ← doubler, jamais « + 2 »
        T* nouveau = new T[capacite];
        for (int i = 0; i < taille; i++) nouveau[i] = donnees[i];
        delete[] donnees;                   // on rend l'ancienne zone
        donnees = nouveau;
    }

public:
    Tableau(int cap = 8) : taille(0), capacite(cap) { donnees = new T[capacite]; }
    ~Tableau() { delete[] donnees; }

    void ajouter(const T& v) {              // O(1) AMORTI
        if (taille == capacite) agrandir();  // la case manque : on s'agrandit
        donnees[taille++] = v;
    }

    T& operator[](int i) { return donnees[i]; }     // O(1), sans vérification
    int getTaille() const { return taille; }
};

Un ajout est presque toujours instantané ; de loin en loin, il déclenche une recopie complète. Toute la question est : à quelle fréquence ?

Le mot amorti désigne cette moyenne, et il mérite mieux qu'une définition. Reprenons le calcul, parce qu'il explique aussi pourquoi on double au lieu d'ajouter une constante — la question tombe régulièrement, et la mauvaise réponse est celle qui paraît raisonnable.

En doublant. Partant d'une capacité de 1, les recopies ont lieu quand la taille atteint 1, 2, 4, 8, … et elles coûtent respectivement 1, 2, 4, 8, … Le coût total des recopies pour arriver à n éléments est donc 1 + 2 + 4 + … + n, une somme que tu connais : elle vaut à peu près 2n. Réparti sur n ajouts, cela fait deux opérations par ajout en moyenne — une constante. D'où le Θ(1) amorti.

En ajoutant une constante, disons deux cases à chaque fois. Les recopies ont lieu aux tailles 2, 4, 6, 8, … et coûtent 2, 4, 6, 8, … Le coût total est cette fois 2 + 4 + … + n, c'est-à-dire une somme arithmétique, qui vaut de l'ordre de n². Réparti sur n ajouts, cela fait n opérations par ajout : le remplissage entier passe de Θ(n) à Θ(n²). La stratégie d'agrandissement n'est donc pas un réglage, c'est un choix d'ordre de croissance.

Tableau<int> t;          // capacité 8 par défaut, taille 0
t.ajouter(10); t.ajouter(23); t.ajouter(7);
t.ajouter(42); t.ajouter(15);

for (int i = 0; i < 8; i++)
    cout << t[i] << " ";

La liste chaînée : le prix de l'accès

Le tableau est excellent pour lire, et mauvais pour insérer ailleurs qu'à la fin : glisser un élément au milieu oblige à décaler d'un cran tout ce qui suit. La liste chaînée renverse exactement ce compromis.

La brique est le nœud : une valeur, et l'adresse du nœud suivant. On garde un seul point d'entrée, la tête, et le dernier nœud pointe vers nullptr — c'est ainsi qu'on sait qu'on est arrivé au bout. La figure met les deux dispositions l'une sous l'autre, avec le même contenu.

Le code qui suit est le plus important du module. Il contient trois choses : le patron de parcours, l'insertion en tête, et la suppression — et c'est la suppression qui révèle la vraie contrainte d'une liste simplement chaînée.

template<typename T>
class ListeChainee {
private:
    struct Noeud {
        T      valeur;
        Noeud* suivant;
        Noeud(const T& v) : valeur(v), suivant(nullptr) { }
    };

    Noeud* tete;
    int    taille;

public:
    ListeChainee() : tete(nullptr), taille(0) { }

    ~ListeChainee() {                        // libère CHAQUE nœud, pas juste la tête
        while (tete != nullptr) {
            Noeud* aSupprimer = tete;
            tete = tete->suivant;            // on avance AVANT de détruire
            delete aSupprimer;
        }
    }

    void insererDebut(const T& v) {          // O(1) : aucun parcours
        Noeud* n = new Noeud(v);
        n->suivant = tete;                   // 1. le neuf pointe vers l'ancienne tête
        tete = n;                            // 2. le neuf devient la tête
        taille++;
    }
};

L'ordre des deux lignes d'insererDebut n'est pas négociable : écrire tete = n d'abord perdrait l'adresse de l'ancienne tête, et toute la liste avec.

Le destructeur mérite un regard, parce qu'il illustre une règle du module précédent dans le cas le plus fréquent du cours. Détruire l'objet ListeChainee ne détruit aucun nœud : les nœuds sont dans le tas, et rien ne les touche sans un delete. Il faut donc parcourir et détruire un par un — et retenir l'adresse du suivant avant de détruire le nœud courant, faute de quoi on détruirait le seul chemin vers le reste de la liste.

// Visiter tous les nœuds, du premier au dernier.
for (Noeud* courant = tete; courant != nullptr; courant = courant->suivant) {
    // ... traiter courant->valeur
}

// La VARIANTE de suppression : on s'arrête sur le nœud d'AVANT,
// parce qu'une liste simple ne sait pas revenir en arrière.
Noeud* courant = tete;
while (courant->suivant != nullptr && courant->suivant->valeur != v)
    courant = courant->suivant;
// ici, courant->suivant est le nœud à retirer (ou nullptr : absent)

Une dernière chose avant de quitter la liste simple, et c'est celle qui coûte le plus de points quand on l'oublie : toute opération sur une liste a trois cas limites, et ils se vérifient dans cet ordre. La liste vide, où tete vaut nullptr et où il n'y a rien à parcourir. La liste d'un seul élément, où la tête est aussi le dernier nœud, donc où toute mise à jour de fin touche la tête. Et surtout le cas où l'élément visé est la tête elle-même — qui se traite à part, puisqu'il n'a pas de prédécesseur dont on pourrait modifier le champ : c'est l'attribut tete de la liste qu'il faut déplacer, et non le suivant d'un nœud.

Prends l'habitude de te poser les trois questions avant d'écrire le corps d'une méthode, plutôt qu'après avoir vu le programme planter : et si la liste est vide ? et s'il n'y a qu'un élément ? et si c'est la tête ? Un correcteur les cherche, et une copie qui les traite explicitement se distingue immédiatement.

void insererFin(const T& v) {
    Noeud* n = new Noeud(v);
    if (tete == nullptr) { tete = n; }
    else {
        Noeud* courant = tete;
        while (courant->suivant != nullptr)
            courant = courant->suivant;
        courant->suivant = n;
    }
    taille++;
}

Ce que le second pointeur achète

On vient de voir qu'une liste simplement chaînée ne sait pas revenir en arrière, et que ça lui coûte cher sur deux opérations : supprimer un nœud qu'on tient, et atteindre l'avant-dernier. La liste doublement chaînée règle les deux d'un coup, en donnant à chaque nœud un second pointeur — vers le précédent.

Le gain se raconte en une phrase : si tu tiens un pointeur sur le nœud à supprimer, tu tiens aussi ses deux voisins, donc tu peux les rebrancher l'un sur l'autre sans parcourir quoi que ce soit. La suppression passe de Θ(n) à Θ(1) — à condition, toujours, d'avoir déjà le pointeur.

Le code ci-dessous ne montre que la suppression, parce que c'est la seule méthode où le double chaînage change quelque chose de visible. Les quatre lignes de rebranchement suivent toutes le même schéma : on traite chaque voisin, et le cas où ce voisin n'existe pas.

struct Noeud {
    T      valeur;
    Noeud* precedent;
    Noeud* suivant;
    Noeud(const T& v) : valeur(v), precedent(nullptr), suivant(nullptr) { }
};

Noeud* tete;
Noeud* queue;

// Retirer un nœud dont on a DÉJÀ le pointeur : O(1), aucun parcours.
void supprimerNoeud(Noeud* n) {
    if (n->precedent) n->precedent->suivant = n->suivant;
    else              tete = n->suivant;      // n était la tête

    if (n->suivant)   n->suivant->precedent = n->precedent;
    else              queue = n->precedent;   // n était la queue

    delete n;
    taille--;
}

Les deux else sont les cas de bord : quand le nœud retiré était à une extrémité, il n'y a pas de voisin à rebrancher — c'est la liste elle-même qu'il faut corriger.

Ce que ce second pointeur coûte est aussi net que ce qu'il achète, et il faut savoir le chiffrer : une adresse de plus par nœud. Sur une machine courante, une adresse occupe huit octets. Une liste doublement chaînée d'entiers — quatre octets de donnée utile — dépense donc seize octets de liens pour quatre octets de contenu : cinq fois la place qu'un tableau aurait prise pour le même contenu. Sur des objets volumineux, la proportion devient négligeable ; sur des entiers, elle est décisive.

Le second coût est plus insidieux : chaque opération doit maintenir deux fois plus d'invariantes. Une insertion touche quatre pointeurs au lieu de deux, et en oublier un seul produit une liste qui se parcourt correctement dans un sens et se perd dans l'autre. C'est un bogue difficile à voir, parce que la moitié des tests passent.

~ListeDouble() {
    delete tete;
    delete queue;
}

La pile : dernier entré, premier sorti

À partir d'ici, on ne construit plus des dispositions mémoire : on construit des disciplines. Une pile et une file contiennent les mêmes éléments et se construisent avec les mêmes briques ; ce qui les sépare est une règle sur qui a le droit de sortir.

La pile suit la règle LIFO — last in, first out, dernier entré, premier sorti. On ajoute au sommet, on retire au sommet, et on ne touche à rien d'autre.

Le TAD Pile admet les deux dispositions du module, et c'est le meilleur exemple de la distinction entre un type abstrait et son implémentation : les deux versions ci-dessous ont exactement la même interface, et elles n'ont pas une ligne en commun.

// AVEC UN TABLEAU — le sommet est la dernière case occupée.
template<typename T>
class PileTableau {
    T*  donnees;
    int taille, capacite;
public:
    void empiler(const T& v) { donnees[taille++] = v; }   // O(1)
    T    depiler()           { return donnees[--taille]; } // O(1)
    T    sommet() const      { return donnees[taille - 1]; }
    bool estVide() const     { return taille == 0; }
};

// AVEC UNE LISTE — le sommet est la TÊTE, jamais la fin :
// insérer et retirer en tête coûtent O(1), en fin O(n).
template<typename T>
class PileListe {
    struct Noeud {
        T      valeur;
        Noeud* suivant;
        Noeud(const T& v) : valeur(v), suivant(nullptr) { }
    };
    Noeud* sommetNoeud;
public:
    void empiler(const T& v) {                            // O(1)
        Noeud* n = new Noeud(v);
        n->suivant = sommetNoeud;
        sommetNoeud = n;
    }
};

Le détail qui compte dans la seconde : on empile en tête. Une pile bâtie sur la fin d'une liste simplement chaînée serait en Θ(n) à chaque opération.

Ces deux implémentations ont la même complexité partout — du Θ(1) sur les trois opérations. Comment choisit-on, alors ? Sur ce que le Θ ne dit pas. Le tableau range ses éléments côte à côte, et un processeur qui lit une case charge automatiquement ses voisines dans sa mémoire rapide ; les accès suivants sont alors quasi gratuits. Les nœuds d'une liste sont dispersés dans le tas, et chaque saut est une nouvelle recherche. À complexité égale, la version tableau gagne en pratique, et c'est d'ailleurs ce que fait la bibliothèque standard.

Reste la faute que le module précédent annonçait, et qu'on retrouve mot pour mot ici : ni empiler ni depiler ne vérifient quoi que ce soit.

Il vaut la peine de savoir où les piles servent, parce que les énoncés d'examen décrivent souvent un problème sans nommer la structure. Quatre usages reviennent : la vérification de parenthèses équilibrées, l'annulation d'actions — la dernière faite est la première défaite —, le parcours en profondeur d'un graphe ou d'un arbre, et la pile d'appels du processeur, qui est littéralement la structure de ce module : chaque appel de fonction empile son contexte, chaque retour le dépile. C'est aussi ce qui explique qu'une récursion sans fin provoque un débordement de pile.

La file : premier entré, premier sorti

La file suit la règle inverse, FIFO — first in, first out. Le premier arrivé est le premier servi. On ajoute d'un côté, on retire de l'autre.

Cette différence a une conséquence directe sur l'implémentation, et c'est elle qui rend la file plus intéressante que la pile. Une pile n'a qu'un point de travail ; une file en a deux, aux extrémités opposées. Or aucune des deux dispositions ne rend les deux extrémités rapides gratuitement.

Voyons pourquoi le tableau naïf échoue ici. Si on enfile à la fin et qu'on défile par le début, chaque défilement laisse un trou en tête : il faut décaler tous les éléments d'un cran pour le combler. Ce décalage coûte Θ(n), à chaque défilement, ce qui rend la structure inutilisable dès que la file s'allonge.

La liste chaînée, elle, s'en sort — à condition de garder ce second pointeur dont l'exercice de la section sur la liste parlait déjà. Le code ci-dessous n'a d'intérêt que pour une chose : montrer que les deux extrémités sont tenues en permanence, et que c'est ce qui rend les deux opérations constantes.

template<typename T>
class FileListe {
private:
    struct Noeud {
        T      valeur;
        Noeud* suivant;
        Noeud(const T& v) : valeur(v), suivant(nullptr) { }
    };

    Noeud* tete;      // par où l'on DÉFILE
    Noeud* queue;     // par où l'on ENFILE
    int    taille;

public:
    FileListe() : tete(nullptr), queue(nullptr), taille(0) { }

    void enfiler(const T& v) {                    // O(1)
        Noeud* n = new Noeud(v);
        if (queue) queue->suivant = n;             // on attache derrière
        else       tete = n;                       // file vide : n est aussi la tête
        queue = n;
        taille++;
    }

    T defiler() {                                  // O(1)
        T v = tete->valeur;
        Noeud* aSupprimer = tete;
        tete = tete->suivant;
        if (!tete) queue = nullptr;                // la file s'est vidée
        delete aSupprimer;
        taille--;
        return v;
    }
};

Les deux lignes de cas limite — else tete = n et if (!tete) queue = nullptr — traitent la même situation vue des deux bouts : la file passe de vide à pleine, ou de pleine à vide.

Les usages de la file se reconnaissent à un mot dans l'énoncé : équité, ou ordre d'arrivée. Le parcours en largeur d'un graphe, qui reviendra dans un module ultérieur, en est le cas central. Viennent ensuite les files de messages ou d'événements, la file d'impression, et la communication entre deux parties d'un programme qui ne vont pas à la même vitesse.

Le modulo qui recycle les cases

On aimerait quand même une file bâtie sur un tableau — pour la localité mémoire dont on parlait à propos de la pile. Le problème était le décalage à chaque défilement ; l'astuce consiste à ne pas décaler du tout, et à laisser les deux extrémités se promener dans le tableau.

L'outil qui fait tourner un indice est le modulo : écrire indice = (indice + 1) % capacite avance d'une case, sauf à la dernière, où l'opération ramène à 0. Une seule expression pour les deux cas — c'est toute l'astuce, et elle tient sur une ligne.

La figure montre la même file avant et après deux enfilages qui franchissent le tour. Ce qu'il faut y suivre est la position des deux indices, pas le contenu des cases.

Le code tient en deux méthodes de quatre lignes, et la ligne qui compte est la même dans les deux. Regarde uniquement les deux %.

template<typename T>
class FileCirculaire {
private:
    T*  donnees;
    int capacite;
    int taille;       // INDISPENSABLE : voir plus bas
    int debut;        // le plus ancien élément
    int fin;          // la prochaine case LIBRE

public:
    void enfiler(const T& v) {                   // O(1)
        donnees[fin] = v;
        fin = (fin + 1) % capacite;               // ← le tour se fait ici
        taille++;
    }

    T defiler() {                                 // O(1)
        T v = donnees[debut];
        debut = (debut + 1) % capacite;           // ← et ici
        taille--;
        return v;
    }

    bool estVide()   const { return taille == 0; }
    bool estPleine() const { return taille == capacite; }
};

La bibliothèque standard nomme ces deux extrémités front et back ; le cours les nomme debut et fin. Ce sont les mêmes notions.

L'attribut taille mérite une explication, parce qu'il a l'air redondant — on pourrait croire que debut et fin suffisent à tout savoir. Ils ne suffisent pas, et voici pourquoi. Quand la file est vide, l'indice de début a rattrapé celui de fin. Quand elle est pleine, la prochaine case libre est justement celle du plus ancien élément : les deux indices coïncident encore. La même configuration décrit donc deux situations opposées, et aucun test sur les indices seuls ne peut les distinguer.

Garder un compteur tranche la question en une comparaison. Ce n'est pas la seule solution — on peut aussi sacrifier une case pour que les deux situations cessent de se ressembler —, mais c'est la plus lisible, et c'est celle que le cours emploie.

Enfin, la méthode pour dérouler une file circulaire à la main, parce que c'est un exercice classique et qu'il se rate en allant trop vite. Trois gestes. Un : partir de debut, qui est toujours le plus ancien élément — jamais de fin. Deux : avancer en ajoutant 1 modulo la capacité, autant de fois qu'il y a d'éléments, c'est-à-dire taille fois. Trois : vérifier — la dernière position obtenue doit être celle qui précède fin. Si elle ne l'est pas, on a compté un cran de trop ou de trop peu.

Quand l'ordre n'est plus l'arrivée

Dernière discipline du module, et la seule qui n'a pas de rapport avec l'ordre d'arrivée. Dans une file avec priorité, chaque élément porte une importance, et c'est elle — et elle seule — qui décide de qui sort le premier.

Le TAD a deux opérations essentielles : inserer, qui ajoute un élément avec sa priorité, et extraireMax, qui retire l'élément de plus forte priorité — quel que soit le moment où il est entré. Certains problèmes veulent au contraire le plus petit ; c'est la même structure, avec la comparaison retournée.

Trois implémentations sont possibles, et les comparer est un exercice d'examen à lui seul, parce que le raisonnement est toujours le même : qui fait le travail, celui qui insère ou celui qui extrait ?

Les deux premières lignes sont un choix de qui paie : si un problème insère énormément et extrait rarement, la liste non triée est excellente, et l'inverse vaut pour la liste triée. Mais dès que les deux opérations sont fréquentes — ce qui est le cas général —, aucune des deux ne convient, puisque chacune a un Θ(n) quelque part.

Le monceau binaire est la réponse à ce cas général, et il est en dehors de ce module : c'est un arbre, donc il brise la contrainte « un seul voisin de chaque côté » sur laquelle tout le reste repose. Le module à venir sur les arbres et les monceaux le construira. Ce qu'il faut en retenir ici tient en une ligne : une file avec priorité efficace se fait avec un monceau, et les deux opérations y coûtent Θ(log n).

Un mot sur les usages, parce qu'ils reviendront : l'ordonnancement de tâches, la simulation à événements discrets, et surtout l'algorithme de plus court chemin de Dijkstra, dont la file avec priorité est le moteur.

Choisir, et savoir dire pourquoi

Le module se termine par ce que l'examen demande vraiment : non pas réciter des complexités, mais justifier un choix. Le tableau ci-dessous rassemble tout ce qui précède, et il se lit en colonnes — chacune est une structure, et ses forces et ses faiblesses se répondent.

Trois lignes de ce tableau sont des pièges de lecture, et il vaut mieux les avoir vues avant l'examen que pendant.

« Pointeur en main » n'est pas une formule de style. L'insertion au milieu d'une liste est en Θ(1) à condition qu'on tienne déjà le nœud d'avant. Si on ne le tient pas, il faut le trouver, et trouver coûte Θ(n). Une question d'examen qui dit « insérer après le k^e élément » décrit donc un Θ(n), alors que la même opération « insérer après ce nœud » décrit un Θ(1). C'est la distinction entre trouver et faire, et c'est elle qui départage les copies.

La recherche est en Θ(n) partout. Aucune structure de ce module n'aide à chercher — et c'est précisément le manque que les modules suivants viendront combler, avec les arbres et les tables de dispersion. Si un problème est dominé par la recherche, la bonne réponse n'est dans aucune colonne de ce tableau.

La dernière ligne se chiffre. Une adresse pèse huit octets sur une machine courante. Pour des entiers de quatre octets, une liste simple triple donc l'occupation mémoire et une liste double la quintuple. C'est un argument recevable en examen quand on justifie un choix — au même titre qu'une complexité.

Voici enfin la règle de décision, qui condense tout le module en cinq lignes. Elle s'applique dans l'ordre : la première condition qui correspond donne la réponse.

Reste ce que la bibliothèque standard fournit déjà, parce que les travaux pratiques demandent d'implémenter à la main mais que les énoncés nomment ces types-là. Les complexités sont les mêmes que celles qu'on vient d'établir — ce sont les mêmes structures.

Deux détails de vocabulaire, qui font trébucher. stack::pop et queue::pop retirent l'élément sans le renvoyer : pour l'obtenir, il faut appeler top ou front avant. Et list n'offre pas d'accès par indice du tout — pas de [] —, ce qui est cohérent avec le tableau ci-dessus : fournir une opération en Θ(n) sous une syntaxe qui suggère du Θ(1) serait un piège permanent.

bool aUnCycle(Noeud* tete) {
    Noeud* lent   = tete;
    Noeud* rapide = tete;
    while (rapide != nullptr && rapide->suivant != nullptr) {
        lent   = lent->suivant;              // un pas
        rapide = rapide->suivant->suivant;   // deux pas
        if (lent == rapide) return true;
    }
    return false;
}