#Tableaux et listesCopier le lien

Prérequis: boucles, fonctions et classes Python; lecture des notations O, Θ et du coût amorti (voir Complexité des algorithmes).

À la fin de ce chapitre, vous saurez:

• Décrire l'invariant de chaque représentation (contiguë contre chaînée) et ce qu'il rend possible.
• Établir le tableau des coûts: accès, insertion, suppression, aux extrémités et au milieu.
• Choisir entre list, deque et numpy.ndarray selon l'usage dominant, et le justifier.

#Deux représentations, deux invariantsCopier le lien

Tableau dynamique. Les éléments occupent des emplacements mémoire contigus; l'adresse de l'élément d'indice i se calcule directement: adresse = base + i × taille_case. C'est cet invariant de contiguïté qui donne l'accès indexé en O(1) et rend le parcours amical pour le cache. En contrepartie, insérer en position i décale vers la droite tous les éléments suivants. Quand la place manque, l'implémentation réserve un bloc double et recopie tout: un append isolé peut donc coûter O(n), mais la séquence d'appels reste en O(1) amorti (analyse par agrégation: après un doublement, les insertions suivantes remboursent la copie).

La formule d'adressage mérite d'être écrite exactement, car c'est elle qui justifie le O(1). Si le tableau commence à l'adresse mémoire base et que chaque case occupe w octets, l'élément d'indice i (numérotation à partir de 0) occupe les octets base + i·w à base + (i+1)·w − 1; avec une numérotation à partir de 1, c'est base + (i−1)·w. Le point crucial est que w soit constant: l'adresse se calcule par une multiplication et une addition, sans parcourir les cases précédentes, d'où le temps constant quelle que soit la valeur de i.

Cette hypothèse tombe dès que les éléments ont des tailles variables. La solution standard est de stocker non pas les objets eux-mêmes mais des pointeurs vers eux: la taille d'un pointeur est la même pour tous, la formule d'adressage reste valide, et il faut ensuite suivre le pointeur pour atteindre l'objet. C'est exactement ce que fait une list Python: le tableau contigu contient des références de taille fixe, pas les objets — d'où un parcours séquentiel rapide mais un saut de pointeur par élément pour lire la valeur.

Liste chaînée. Chaque maillon porte sa valeur et un pointeur vers le suivant. Plus de contiguïté: atteindre le iᵉ maillon impose d'en traverser i, soit O(n). En échange, insérer ou supprimer un maillon voisin d'un maillon déjà connu ne touche que deux pointeurs: O(1). La variante doublement chaînée ajoute un pointeur vers le précédent et permet la suppression en O(1) à partir du maillon lui-même.

#Tableaux multidimensionnels: ligne-majeur et colonne-majeurCopier le lien

Une matrice n'est pas une structure de base: c'est un tableau à une dimension plus une convention d'indexation. Pour une matrice M de r lignes et c colonnes stockée dans un seul tableau, deux conventions s'opposent.

Ordre ligne-majeur (ligne après ligne): les r lignes sont écrites à la suite. En numérotant à partir de 1, l'élément M[i, j] se trouve à l'indice

(i − 1)·c + j

Ordre colonne-majeur (colonne après colonne): les c colonnes sont écrites à la suite, et

(j − 1)·r + i

Pour la matrice 2 × 3 dont les lignes sont (1, 2, 3) et (4, 5, 6), l'ordre ligne-majeur donne 1 2 3 4 5 6 et l'ordre colonne-majeur 1 4 2 5 3 6. Le calcul d'adresse reste en temps constant dans les deux cas: c'est la même formule qu'en une dimension, à un changement de variable près.

Le choix n'est pas cosmétique, il décide de la localité mémoire. Un parcours ligne par ligne sur une matrice stockée en colonne-majeur saute une ligne entière à chaque pas; le cache est mis à mal et le parcours peut être plusieurs fois plus lent, à complexité identique. C'est la raison pour laquelle le langage C (et numpy par défaut) utilise l'ordre ligne-majeur, tandis que Fortran, MATLAB et numpy en mode order='F' utilisent l'ordre colonne-majeur: chacun privilégie le parcours naturel de sa communauté. La règle pratique: faire varier l'indice le plus à droite dans la boucle la plus interne.

Une variante utile est la représentation multi-tableaux: un tableau de r pointeurs, chacun vers un tableau de c éléments (une ligne). Elle autorise les tableaux irréguliers (des lignes de longueurs différentes), au prix d'un saut de pointeur par ligne et d'allocations séparées. Une troisième voie, la représentation par blocs, découpe la matrice en blocs stockés contigus — utile pour les algorithmes de multiplication par blocs et les architectures à cache hiérarchique.

#Quand l'un brille plus que l'autreCopier le lien

Accès par index nombreux, parcours séquentiels, ajouts en fin: le tableau dynamique gagne. Insertions ou suppressions locales fréquentes, position déjà atteinte par un parcours: la liste chaînée ou une deque reprend l'avantage. Retirer en tête doit toujours vous alerter: sur un tableau, pop(0) décale tout le contenu.

#Les variantes de listes chaînéesCopier le lien

Quatre choix indépendants définissent une liste chaînée; les nommer évite la moitié des bugs:

Dans la suite on suppose, comme le cours, une liste non triée et doublement chaînée, avec un attribut head pointant sur la tête. La convention: x.prev == NIL signifie que x est la tête, x.next == NIL que x est la queue, et head == NIL que la liste est vide.

#Les quatre opérations élémentairesCopier le lien

Recherche. Elle parcourt la liste du début jusqu'à trouver la clé, en temps linéaire.

1LIST-SEARCH(L, k)21  x = L.head32  tant que x ≠ NIL et x.key ≠ k43      x = x.next54  renvoyer x

Coût: Θ(n) dans le pire cas (la clé est en queue ou absente). Aucun ordre n'est supposé, donc aucune recherche binaire n'est possible; c'est le prix structurel de la liste chaînée, et il ne se paie pas en O(1) comme on le croit souvent.

Insertion en tête. Trois réécritures de pointeurs, sans jamais parcourir la liste.

1LIST-PREPEND(L, x)21  x.next = L.head32  x.prev = NIL43  si L.head ≠ NIL54      L.head.prev = x65  L.head = x

Coût: Θ(1) sur une liste de n éléments.

Insertion après un maillon connu.

1LIST-INSERT(x, y)          // insérer y juste après x21  y.next = x.next32  y.prev = x43  si x.next ≠ NIL54      x.next.prev = y65  x.next = y

Coût: Θ(1). Remarque: la procédure ne prend pas la liste en paramètre, parce qu'elle ne touche jamais head — elle n'a besoin que du maillon x. Cette signature est un indice de conception: une opération locale ne devrait pas dépendre de la structure globale.

Suppression d'un maillon connu.

1LIST-DELETE(L, x)21  si x.prev ≠ NIL32      x.prev.next = x.next43  sinon54      L.head = x.next65  si x.next ≠ NIL76      x.next.prev = x.prev

Coût: Θ(1) — mais uniquement parce qu'on reçoit un pointeur sur le maillon, pas une clé. Pour supprimer par clé, il faut d'abord la trouver: LIST-SEARCH ramène le coût du pire cas à Θ(n). L'énoncé « la suppression dans une liste chaînée est en O(1) » n'est vrai que sous cette hypothèse, qu'il faut toujours énoncer.

Exercice. Montrez que, dans une liste simplement chaînée, supprimer un maillon pointé par x coûte Θ(n) dans le pire cas.

Correction: on dispose de x mais pas de son prédécesseur, et next n'est pas réversible. Pour recâbler pred.next = x.next, il faut d'abord trouver pred — donc parcourir la liste depuis la tête jusqu'au maillon dont le next est x, ce qui coûte Θ(n) dans le pire cas (x en queue). Il existe une astuce en Θ(1) si x n'est pas la queue: recopier dans x le contenu de x.next, puis supprimer x.next (dont on connaît le prédécesseur, qui est x). Mais elle échoue sur la queue, et elle invalide tout pointeur extérieur vers x.next: elle ne remplace pas un prev. C'est le compromis exact que paie le double chaînage — un pointeur de plus par maillon pour supprimer en O(1) partout.

#Sentinelles: supprimer les cas de bordCopier le lien

Le code de LIST-DELETE a deux tests de bord (lignes 1 et 5), et celui de LIST-PREPEND un troisième. Ces cas particuliers sont la principale source d'erreurs d'implémentation. La parade est un maillon factice, la sentinelle L.nil, qui n'est jamais supprimé et se place entre la tête et la queue: la liste devient circulaire et non vide par construction. L.nil.next est la tête, L.nil.prev la queue, et une liste vide est celle où L.nil.next == L.nil et L.nil.prev == L.nil.

Avec une sentinelle, LIST-DELETE devient:

1LIST-DELETE'(L, x)21  x.prev.next = x.next32  x.next.prev = x.prev

Plus aucun test. Le coût des deux versions est le même en Θ(1); la sentinelle ne fait gagner qu'un facteur constant, mais elle élimine trois cas de bord — et c'est en pratique le gain décisif. Elle coûte une case mémoire supplémentaire par liste, ce qui n'est pas neutre quand on manipule des millions de petites listes: c'est la raison pour laquelle elle est systématique dans les implémentations de listes circulaires (noyaux, allocateurs, std::list en C++) et absente des structures où chaque nœud compte.

#Exemple tracé: insertion triée dans une liste chaînéeCopier le lien

Invariant: après chaque insertion, la liste parcourue du début à la fin est triée strictement croissante.

1def insert_sorted(head, x):2    # Cas 1: liste vide, ou x avant la tête3    if head is None or x < head.val:4        return Noeud(x, head)          # nouvelle tête5    # Cas 2: avancer jusqu'au premier maillon dont le suivant dépasse x6    cur = head7    while cur.next is not None and cur.next.val < x:8        cur = cur.next9    # Cas 3: glisser le nouveau maillon entre cur et cur.next10    cur.next = Noeud(x, cur.next)11    return head

Trace sur la liste 1 → 3 → 7 avec x = 5:

Coût: O(n) pour la recherche de la position, O(1) pour le recâblage. La recherche domine toujours; la liste rend le recâblage gratuit, pas la recherche.

#Visualiser le coût d'une insertionCopier le lien

#Structures Python: ce que chaque type garantitCopier le lien

• list: tableau dynamique. Indexation O(1), append O(1) amorti, mais insert(0, x) et pop(0) coûtent O(n) car tout le contenu se décale.
• collections.deque: liste doublement chaînée par blocs. append et popleft en O(1); pas d'accès indexé rapide.
• numpy.ndarray: bloc mémoire contigu et typé, optimisé pour le calcul vectorisé sur des données homogènes.

#Exercice 1: deux files correctes, des vitesses opposéesCopier le lien

Objectif: constater que deux implémentations correctes peuvent différer d'un facteur élevé en vitesse.

1import time2from collections import deque3 4def file_avec_liste(n):5    f = []6    for i in range(n):7        f.append(i)          # O(1) amorti8    for _ in range(n):9        f.pop(0)             # O(n) chaque fois: la file recule10 11def file_avec_deque(n):12    f = deque()13    for i in range(n):14        f.append(i)          # O(1)

Correction: les deux versions défilent bien 0, 1, 2, ..., n−1 dans l'ordre d'arrivée, la correction est identique. La performance diverge: file_avec_liste exécute environ n²/2 décalages d'éléments, cinq milliards pour n = 100 000, contre cent mille opérations O(1) pour la deque.

Vérification: chronométrez pour n = 10 000, 30 000 puis 100 000. Le temps de file_avec_liste doit croître environ comme n² (×9 quand n triple), celui de file_avec_deque presque linéairement.

#Exercice 2: que cache le « O(1) si position atteinte »?Copier le lien

Question: pourquoi la précision « position déjà atteinte » dans le tableau des coûts change-t-elle l'analyse, et que devient le coût total d'une insertion au milieu d'une liste ?

Correction: le O(1) de la liste chaînée ne couvre que le recâblage de deux pointeurs. Atteindre la position demande un parcours depuis la tête, O(n) au pire. Une insertion « quelque part au milieu » coûte donc O(n) en liste chaînée (parcours) comme en tableau (décalage): mêmes ordres de grandeur, constantes différentes. La liste ne gagne que si le parcours est déjà payé: itérateur conservé, suppression pendant un balayage, insertions groupées autour d'une même zone.