Français
Menu

Tableau vs liste chaînée : accès, insertion et suppression, disposition en mémoire, cache, complexité temporelle

Un tableau range des éléments de même type côte à côte en mémoire, sans trou, si bien que la position de n’importe quel élément se calcule à partir de son indice et qu’on peut le lire ou l’écrire en temps constant. Une liste chaînée est une structure de données dans laquelle chaque élément contient une valeur et un pointeur vers l’élément suivant ; les éléments sont reliés en suivant ces pointeurs et peuvent donc se trouver à des endroits différents de la mémoire. Un tableau se lit vite, mais insérer ou supprimer au milieu oblige à décaler les éléments qui suivent. Une liste chaînée peut insérer ou supprimer en changeant seulement des pointeurs une fois la position connue, mais lire le i-ième élément oblige à la parcourir depuis la tête. Règle de base : un tableau quand on lit surtout par indice, une liste chaînée quand on insère ou supprime souvent à des positions connues.

CritèreTableauListe chaînée
Disposition en mémoireLes éléments sont côte à côte dans un seul bloc contiguLes éléments sont dispersés et reliés par des pointeurs
Lecture du i-ième élémentO(1) : l’adresse vaut adresse de départ + i × taille d’un élémentO(n) : suivre i fois les pointeurs depuis la tête
Recherche d’une valeurO(n) par recherche linéaire si non trié ; O(log n) par recherche dichotomique si triéO(n), même si trié ; la recherche dichotomique est impossible faute de pouvoir sauter au milieu
Insertion ou suppression au milieuO(n) : les éléments qui suivent sont décalés un à unO(1) si la position (l’élément précédent) est connue ; seuls des pointeurs changent
Ajout en finO(1) s’il reste de la place ; un tableau dynamique qui double sa capacité recopie parfois tout, mais reste O(1) en moyenne (amorti)O(1) si l’on conserve un pointeur vers le dernier élément
RedimensionnementLa taille d’un tableau de taille fixe est fixée à sa création ; l’agrandir impose d’allouer un nouveau bloc et de recopierL’espace est alloué élément par élément : la liste ne grandit que du nécessaire
Mémoire utiliséeSeulement les éléments eux-mêmes (un tableau dynamique garde un peu de capacité de réserve)Un pointeur supplémentaire par élément (deux dans une liste doublement chaînée)
Efficacité du cacheBonne : les éléments sont contigus, donc une lecture séquentielle tire bien parti des caches et du préchargementMauvaise : les éléments ont tendance à être dispersés, donc même un parcours en O(n) identique peut être bien plus lent qu’avec un tableau
Usages typiquesTables lues et écrites par indice, matrices et images, données à trier ou à rechercher par dichotomie, implémentation de piles et de filesSéquences avec insertions et suppressions fréquentes, chaînage dans les tables de hachage, gestion de l’espace libre

Les valeurs indiquées sont des ordres de grandeur typiques et varient selon la génération de procédé et le produit.

Quand choisir l'un ou l'autre ?

Tableau
Lorsque les éléments sont surtout lus et écrits par indice ou lus dans l’ordre depuis le début. Comme les caches fonctionnent bien avec eux, les tableaux (y compris dynamiques) sont plus rapides dans beaucoup de situations sur les ordinateurs actuels.
Liste chaînée
Lorsqu’il y a beaucoup d’insertions et de suppressions au milieu et qu’on détient déjà un pointeur vers la position. Comme les éléments sont rechaînés sans être déplacés, on l’utilise aussi quand les adresses des éléments ne doivent pas changer.

Questions fréquentes

L’insertion dans une liste chaînée est en O(1) : pourquoi les tableaux sont-ils parfois plus rapides en pratique ?

Pour deux raisons. D’abord, si le point d’insertion doit être cherché depuis la tête, cette recherche coûte O(n), et l’opération entière est en O(n), comme pour un tableau, même si l’insertion elle-même est en O(1). Ensuite, décaler les éléments d’un tableau est une copie de mémoire contiguë qui tire bien parti des caches et qui est très rapide, alors que parcourir une liste chaînée lit des adresses dispersées un élément à la fois et provoque souvent des défauts de cache. La complexité décrit la croissance du coût avec la taille des données ; la vitesse réelle doit être mesurée.

En quoi les listes simplement et doublement chaînées diffèrent-elles ?

Dans une liste simplement chaînée, chaque élément n’a qu’un pointeur vers l’élément suivant, et on ne peut la parcourir que de l’avant vers l’arrière. Une liste doublement chaînée a aussi un pointeur vers l’élément précédent : on peut donc aussi la parcourir à rebours et, à partir d’un pointeur vers un élément, supprimer cet élément en O(1). En contrepartie, chaque élément a un pointeur de plus, et davantage de pointeurs doivent être mis à jour.

Qu’est-ce qu’un tableau dynamique ?

Un tableau qui peut changer de taille : quand sa capacité est épuisée, il alloue un bloc plus grand et y recopie tout. Si la capacité double à chaque fois, le nombre total de copies n’est qu’environ égal au nombre d’éléments, si bien que l’ajout en fin est en O(1) en moyenne. La lecture par indice est en O(1), comme pour un tableau ordinaire.

Vérifier vos connaissances

Par rapport à un tableau, quelle description d'une liste chaînée (liste dont chaque élément contient un pointeur vers l'élément suivant) est correcte ?

  1. ASi l'élément situé juste avant le point d'insertion est connu, on peut insérer un nouvel élément en modifiant seulement des pointeurs, sans déplacer les autres éléments ; en revanche, lire le i-ème élément oblige à parcourir la liste depuis le début
  2. BLa position du i-ème élément se calcule, si bien que n'importe quel élément se lit en temps constant, O(1)
  3. CLes éléments sont rangés de façon contiguë en mémoire, si bien que le cache et le préchargement fonctionnent bien lors d'une lecture dans l'ordre
Afficher la réponse et l'explication

Réponse : A. Si l'élément situé juste avant le point d'insertion est connu, on peut insérer un nouvel élément en modifiant seulement des pointeurs, sans déplacer les autres éléments ; en revanche, lire le i-ème élément oblige à parcourir la liste depuis le début

Dans une liste chaînée, une fois la position connue, l'insertion et la suppression ne demandent que la réécriture des pointeurs voisins, en O(1). Lire le i-ème élément oblige en revanche à suivre i pointeurs depuis le début, en O(n). Un tableau calcule l'adresse du i-ème élément à partir de son adresse de départ et de la taille d'un élément, et lit donc n'importe quel élément en O(1), mais une insertion au milieu coûte O(n) pour décaler les éléments suivants. De plus, les éléments d'un tableau étant contigus, le cache et le préchargement fonctionnent bien, alors que les nœuds d'une liste chaînée ont tendance à être dispersés en mémoire, si bien que même un parcours en O(n) peut être beaucoup plus lent.

Un tableau dynamique, quand on ajoute un élément alors qu'il est plein, alloue une nouvelle zone de capacité double et y copie tous les éléments. Si l'on ajoute un à un 1000 éléments à un tableau vide de capacité 1, combien de copies d'éléments sont effectuées au total ?

  1. A10
  2. B1023
  3. C499 500
Afficher la réponse et l'explication

Réponse : B. 1023

La capacité double à chaque fois qu'elle est atteinte, en passant par 1, 2, 4, …, 512, et à chaque fois tous les éléments présents sont copiés : le nombre total de copies vaut donc 1 + 2 + 4 + … + 512 = 1023. Pour 1000 ajouts, cela fait environ une copie par élément : le coût par ajout est constant en moyenne, soit O(1) amorti. Si la capacité n'augmentait que de 1 à chaque fois, les copies totaliseraient 1 + 2 + … + 999 = 499 500, soit O(n²). 10 est le nombre de réallocations, pas le nombre d'éléments copiés.

Quelle comparaison du chaînage (relier par une liste chaînée les éléments d'une même position) et de l'adressage ouvert (chercher une autre position libre dans la table), comme méthodes de résolution des collisions d'une table de hachage, est correcte ? Le facteur de charge est le nombre d'éléments stockés divisé par la taille de la table.

  1. ALe chaînage peut stocker des éléments même quand le facteur de charge dépasse 1, alors que l'adressage ouvert ne peut pas stocker plus d'éléments que la taille de la table, et son nombre de sondages augmente fortement quand le facteur de charge approche de 1
  2. BL'adressage ouvert n'a pas de collisions, si bien qu'une recherche demande toujours un seul sondage, quel que soit le facteur de charge
  3. CAvec le chaînage, le coût d'une recherche reste le même, aussi élevé que soit le facteur de charge
Afficher la réponse et l'explication

Réponse : A. Le chaînage peut stocker des éléments même quand le facteur de charge dépasse 1, alors que l'adressage ouvert ne peut pas stocker plus d'éléments que la taille de la table, et son nombre de sondages augmente fortement quand le facteur de charge approche de 1

Le chaînage relie en listes les éléments d'une même position : il peut donc stocker plus d'éléments que la taille de la table, mais la longueur moyenne des listes croît proportionnellement au facteur de charge, et le coût de recherche aussi. L'adressage ouvert range tout à l'intérieur de la table : il peut contenir au plus autant d'éléments que la taille de la table, et le nombre de sondages nécessaires pour trouver un emplacement libre augmente fortement quand le facteur de charge approche de 1. Quelle que soit la méthode, on agrandit généralement la table et on réinsère tous les éléments (rehachage) dès que le facteur de charge dépasse une limite choisie, par exemple de 0,5 à 0,75 environ. Les collisions se produisent aussi en adressage ouvert ; celui-ci les traite en cherchant une position libre.

  1. Pour une table de hachage contenant de nombreux éléments et maintenue à un facteur de charge d'environ 0,5, quelle est la raison la plus appropriée pour laquelle l'adressage ouvert avec sondage linéaire tend à être plus rapide que le chaînage (relier les éléments par des listes chaînées) ?
  2. Quelle condition est nécessaire pour utiliser la recherche dichotomique, qui compare la cible à l'élément du milieu et réduit de moitié l'intervalle de recherche à chaque fois ?

Questions d'entraînement sur Structures de données et algorithmes

Termes clés expliqués

Tableau
Structure de données qui range à la suite des valeurs de même type et désigne chaque élément par un indice. Comme les éléments sont stockés de façon contiguë en mémoire, la position de n'importe quel élément se calcule à partir de son indice : chaque élément peut donc être lu ou écrit en temps constant. Certains langages font commencer les indices à 0, certaines notations à 1.
Liste chaînée (linked list)
Structure de données dans laquelle chaque élément contient une valeur et un pointeur vers l'élément suivant, les éléments étant reliés en suivant les pointeurs. Une fois la position connue, l'insertion et la suppression sont des modifications de pointeurs en O(1), mais lire le i-ème élément oblige à parcourir la liste depuis le début, en O(n). Les éléments ont tendance à être dispersés en mémoire, si bien que les caches fonctionnent moins bien qu'avec les tableaux.
Pointeur
Variable dont la valeur est l'adresse mémoire d'une variable, d'un élément de tableau, d'une fonction, etc. En C, on le déclare comme int *p ; &x donne l'adresse de x, et *p lit ou écrit la valeur pointée par p. Ajouter un entier à un pointeur le fait avancer par pas égaux à la taille du type pointé. Dans la plupart des expressions, le nom d'un tableau est converti en pointeur sur son premier élément, si bien que a[i] a le même sens que *(a + i). La valeur qui ne pointe nulle part s'appelle le pointeur NULL.
Complexité temporelle (notation grand O)
Description de la façon dont le travail (complexité temporelle) ou la mémoire (complexité spatiale) nécessaires à un algorithme croissent avec le nombre de données n. Elle s'écrit en notation grand O, par exemple O(n), O(n log n) ou O(n²), en omettant les facteurs constants et les termes de degré inférieur.
Recherche dichotomique (recherche binaire)
Méthode de recherche sur des données triées qui compare la cible à l'élément du milieu et réduit de moitié l'intervalle de recherche à chaque fois. Elle trouve une valeur parmi n données en au plus ⌊log₂ n⌋ + 1 comparaisons, d'où une complexité en O(log n). Les données doivent être triées.
Table de hachage (hash table)
Structure de données qui calcule une position de stockage à partir d'une clé au moyen d'une fonction de hachage, ce qui permet la recherche, l'insertion et la suppression en O(1) en moyenne. Les collisions, où des clés différentes tombent sur la même position, sont traitées par chaînage ou par adressage ouvert.
Localité spatiale
Propriété selon laquelle, après un accès à une adresse, les adresses voisines ont de fortes chances d'être accédées peu après. Exemple : lecture séquentielle d'un tableau. C'est pourquoi les données sont chargées par ligne de cache.

Comparatifs associés