Page principale

La lecture de cette page nécessite des connaissances de base en algorithmique et programmation. Des exemples de codes dans différents langages sont donnés. Il n'est pas nécessaire d'en comprendre tout le détail - l'idée étant plutôt de s'en imprégner.

Listes et tableaux

Listes et tableaux sont avant tout des types de données abstraits, permettant de stocker de façon ordonnée des éléments.

Une liste (ou list en anglais) représente une séquence finie de valeurs. Les opérations typiquement disponibles sur une liste sont l'ajout ou suppression en début (et/ou en fin) de liste, et l'accès à la queue de la liste (i.e. toute la liste à l'exception de la première valeur).
Un tableau (à 1 dimension - il ne sera question que de ce type de tableaux ici) - ou array en anglais - est une structure de données indexable par des entiers - i.e. permettant d'accéder en lecture ou écriture $i$^ème élément.

Cette page traite de trois implémentations de ces types : les tableaux (vus cette fois-ci comme structure de données concrète), les listes chaînées et les tableaux dynamiques (ou vecteurs, ou encore listes-tableaux).

Tableaux (arrays)

Prenons l'exemple d'un tableau de $n$ entiers codés sur 8 bits - où $n\in\mathbb{N}^*$.
Il s'agit simplement d'un bloc contigü de mémoire - constitué de $8n$ bits - contenant les codes correspondant aux $n$ entiers accolés les uns aux autres.

Notons t le tableau, et $x$ son adresse en mémoire. Le premier entier du tableau, noté t[0] dans de nombreux langages, est codé par les bits entre les adresses $x$ à $x+7$. Le second, codé t[1], est codé par les bits entre les adresses $x+8$ et $x+15$, etc.

Passons en revue les avantages et inconvénients de cette structure.

Avantage

On peut accéder en temps constant (ou $O(1)$) - c'est-à-dire indépendant de la taille du tableau - à n'importe quel élément de celui-ci (on parle d'accès direct, ou en anglais de random access). En effet, pour accéder à l'élément t[i], il suffit d'aller à l'adresse mémoire $x+di$ - où $x$ est l'adresse mémoire du début du tableau, et $d$ le nombre de bits correspondant au codage de l'un de ses éléments. En particulier, le premier élément du tableau - t[0] est bien à l'adresse $x$, ce qui explique pourquoi les tableaux ont été historiquement indicés à partir de 0.

Inconvénients

Un tableau a une taille fixée. Dans des langages de bas niveau tels que C, le programmeur doit gérer lui-même l'allocation d'un bloc mémoire de taille correcte lorsqu'il veut créer un tableau, à l'aide de commandes telles que malloc, puis libérer la mémoire une fois le tableau utilisé à l'aide de free.
Corollaire : on ne peut pas ajouter facilement d'élément à un tableau. Ces opérations nécessitent l'allocation d'un nouveau bloc mémoire, puis la recopie des éléments de l'ancien tableau dans le nouveau. Cela s'effectue typiquement en temps linéaire (ou $O(n)$) en la longueur $n$ du tableau - c'est-à-dire proportionnel à celle-ci (les réallocations sont de plus coûteuses, dans le sens où la constante cachée dans le $O$ peut être importante - tout cela dépendant des détails de son implémentation). Cela nécessite de plus de faire une copie en mémoire du tableau initial, d'où une complexité spatiale linéaire. Voici l'algorithme écrit en pseudo-code.

Ajout d'un élément e à la fin d'un tableau t
(On notera $n$ la longueur du tableau, et $d$ le nombre de bits sur lequel est représenté un élément du tableau.)

Allouer un nouvel espace mémoire de longueur $(n+1)d$ - correspondant à un tableau t2 (on notera x2 son adresse mémoire)
Pour i variant de 0 à n-1
Recopier les bits de t[i] dans t2[i].
Écrire le code de e dans t2[n] (i.e. à l'adresse $x+dn$).
Libérer la mémoire occupée par t
Faire pointer t vers t2

Voici un code correspondant dans le langage C, de bas niveau, où la gestion de la mémoire est à la charge du programmeur. Sans rentrer dans le détail de chaque instruction, il est enrichissant de parcourir l'ensemble de ce code pour en comprendre le mécanisme général.

Code C pour l'ajout d'un élément à un tableau

  int n = 100;  //nombre d'éléments du tableau
  //création d'un tableau de 100 entiers
  // -  int * signifie «pointeur vers un entier», i.e. une adresse mémoire où est stockée un entier
  // - malloc est une commande d'allocation mémoire, elle renvoie en cas
  //   de succès un pointeur vers le début du bloc mémoire alloué
  // - il faut théoriquement vérifier si l'allocation a réussi (elle a pu échouer, par exemple si la
  //   mémoire est saturée). Je ne le fais pas ici, pour alléger le code
  int * t = malloc (n * sizeof(int)); 
  
  //remplissage du tableau avec des zéros
  for (int i = 0; i < n; i++) 
    t[i] = 0;
    //t[i] est un raccourci pour «l'entier codé à partir de l'adresse mémoire t+i*sizeof(int)»
  
  ////////Voici maintenant un code possible pour rajouter 0 à la fin de ce tableau:
  //allocation d'un nouveau bloc mémoire (on pourrait utiliser realloc également)
  int * t2 = malloc ((n + 1) * sizeof(int));
  //recopie de t dans t2 (on pourrait également utiliser la commande memcopy)
  for (int i = 0; i < n; i++)
    t2[i] = t[i];

  t2[n] = 0;  //le dernier élément de t2 est mis à 0
  free (t); //libération de la mémoire occupée par t
  t = t2; //on fait pointer t vers le tableau nouvelle créé.

Schématiquement, sur un petit exemple :

À noter que le (mauvais) code Python suivant, qui ajoute un élément à une liste Python (qui est implémentée à l'aide d'un tableau dynamique), fait sensiblement la même chose. Ce type de code doit être évité - car comme nous allons le voir plus loin, les listes Python disposent d'un autre mécanisme plus efficace pour ajouter un élément à la fin.

(Mauvais) code Python pour l'ajout d'un élément à une liste Python

# création d'une liste de 100 zéros
t = [0]*100
# ajouter 1 à la fin du tableau
t = t + [1]

Voici un récapitulatif des complexités des différentes opérations élémentaires sur un tableau.

	Tableau
Accès à un élément	$O(1)$
Ajout d'un élément	$O(n)$
Suppression d'un élément	$O(n)$

Le tableau (concret) présenté dans cette section est donc une bonne implémentation du type de données abstrait «tableau» décrit rapidement en introduction. C'est en revanche une implémentation peu efficace du type de données abstrait «liste», dans la mesure où les opérations de suppression et d'ajout sont coûteuses.

Listes chaînées (linked lists)

Dans cette section, on présente deux structures de données concrètes implémentant spécifiquement le type abstrait «liste».

Listes simplement chaînées

L'élément de base d'une liste simplement chaînée est une cellule constituée de deux parties.

La première contient une donnée - par exemple un entier pour une liste d'entiers.
La seconde contient un pointeur (i.e. une adresse mémoire) vers une autre cellule (ou un pointeur nul).

Une liste est alors une succession de cellules, chacune pointant sur la suivante, et la dernière ayant un pointeur nul - i.e. ne pointant sur rien. En pratique, la variable «contenant» la liste est simplement un pointeur vers la première cellule.

Voici par exemple une représentation d'une liste contenant les entiers 2, 4, 1 et 5.

À noter que les cellules n'ont pas à être placées de façon contigüe en mémoire - ce qui va donner à cette structure plus de souplesse qu'aux tableaux. Par exemple, l'insertion ou la suppression en début de liste s'effectue en temps constant grâce aux algorithmes ci-dessous.

Ajout d'un élément e en début d'une liste l

Créer une nouvelle cellule avec la donnée e et pointant vers l'actuelle première cellule de l
Faire pointer l vers cette nouvelle cellule

Suppression d'un élément en début d'une liste l
(On suppose la liste non-vide.)

Faire pointer l vers le successeur de sa première cellule (éventuellement nul)
Libérer la mémoire correspondant à celle-ci.

Voici un code correspondant en JavaScript.

Code JavaScript pour une classe de Liste, avec les opérations d'ajout et suppression au début.

//Type Cellule - constructeur
function Cell(d, next) {
    this.d = d; //données
    this.next = next; //cellule suivante
}

//Type Liste - constructeur
function List() {
    this.cell = null; //première cellule de la liste
}

//Suppression en début de liste
List.prototype.remove = function() {
    if (this.cell !== null)
	this.cell = this.cell.next;
    else
	throw 'Liste vide !' //on lève une exception si la liste est vide
}

//Ajout en début de liste
List.prototype.add = function(d) {
    let c = new Cell(d, this.cell);
    this.cell = c;
}

On peut également ajouter un élément à la fin d'une liste, insérer un élément à toute position, mais cela nécessitera de parcourir la liste depuis son premier élément jusqu'à la position souhaitée. Ainsi, une insertion ou suppression en position $i$ sera de complexité $O(i)$, et une insertion ou suppression en fin de liste sera de complexité $O(n)$, où $n$ est la longueur de la liste.

Code JavaScript pour la suppression à la fin.

List.prototype.removeEnd = function() {
    if (this.cell == null)
	throw "Liste vide !"; //on lève une exception si la liste est vide
    if (this.cell.next == null) //cas particulier où la liste n'a qu'une cellule
    {
	this.cell = null;
	return;
    }
//parcours de la liste jusqu'à l'avant-dernière cellule
    let cc = this.cell;
    while (cc.next.next !== null)
	cc = cc.next;
    cc.next = null;  //l'avant-dernière cellule ne pointe plus sur rien : 
                             //on a supprimé la dernière cellule.
}

L'application suivante permet de tester de façon imagée ces différentes opérations - les éléments ajoutés étant des entiers compris entre 0 et 9, choisis aléatoirement.

Contenu de la liste :

	Tableau	Liste simplement chaînée
Accès à un élément au début	$O(1)$	$O(1)$
Accès à un élément à la fin	$O(1)$	$O(n)$
Ajout d'un élément au début	$O(n)$	$O(1)$
Ajout d'un élément à la fin	$O(n)$	$O(n)$
Suppression d'un élément au début	$O(n)$	$O(1)$
Suppression d'un élément à la fin	$O(n)$	$O(n)$

Si l'on a besoin d'une structure permettant d'effectuer des opérations rapides à la fin, mais pas nécessairement au début, on utilise exactement la même structure ! Il suffit de changer l'interprétation que l'on fait de l'odre des cellules, et regardant comme première donnée celle de la dernière cellule.

Listes doublement chaînées

Si l'on souhaite disposer d'opérations rapides au début et à la fin de la liste, on peut utiliser une structure de liste doublement chaînée. Chaque cellule contiendra maintenant un pointeur vers la cellule précédente (ou un pointeur nul pour la première cellule). On conserve en permanence dans la structure un pointeur vers la première et vers la dernière cellule. Schématiquement :

Au prix d'un encombrement mémoire plus grand (pour stocker le second pointeur de chaque cellule) et d'un surcoût en nombre d'opérations pour gérer les pointeurs supplémentaires lors d'un ajout ou d'une suppression, on gagne sur plusieurs plans par rapport à une liste simplement chaînée :

Ajout et suppression en début et en fin de liste sont effectuées en temps constant (i.e. indépendant de la longueur de la liste).
Si l'on dispose d'un pointeur direct vers une cellule donnée de la liste, on pourra supprimer celle-ci en temps constant : le double chaînage permet d'accéder en temps constant à ces voisines, dont il suffit de modifier les pointeurs comme sur la figure ci-dessous, où le 2^ème élément de la liste a été supprimé.

	Tableau	Liste simplement chaînée	Liste doublement chaînée
Accès à un élément au début	$O(1)$	$O(1)$	$O(1)$
Accès à un élément à la fin	$O(1)$	$O(n)$	$O(1)$
Accès à un élément au milieu	$O(1)$	$O(n)$	$O(n)$
Ajout d'un élément au début	$O(n)$	$O(1)$	$O(1)$
Ajout d'un élément à la fin	$O(n)$	$O(n)$	$O(1)$
Suppression d'un élément au début	$O(n)$	$O(1)$	$O(1)$
Suppression d'un élément à la fin	$O(n)$	$O(n)$	$O(1)$
Suppression d'une cellule «pointée»^*	$O(n)$	$O(n)$^**	$O(1)$

* Dans le cas d'une liste, on suppose disposer d'un pointeur sur cette cellule
** Avec une liste simplement chaînée, on n'a pas accès à la cellule précédent la cellule à supprimer, dont le chaînage doit pourtaut être modifié : on doit dont parcourrir la liste depuis le début pour trouver cette cellule…

Attention : si les listes simplement et doublement chaînées permettent de gagner en complexité sur certaines opérations, elles en perdent pour ce qui est de l'accès direct. De plus, elle sont plus encombrantes en mémoire (il faut stocker les pointeurs), et le travail sur les pointeurs introduit un surcoût en terme de nombre d'opérations. Il faut donc les utiliser avec discernement, et par exemple ne pas utiliser une liste doublement chaînée là où une liste simplement chaînée suffirait, pour ne pas payer un coût temporel et spatial inutile lié aux pointeurs arrières.

Vecteurs/Tableaux dynamiques (Dynamic array)

L'idée des tableaux dynamiques ou vecteurs est :

de conserver l'accès direct en temps constant comme dans un tableau;
d'éviter la gestion des pointeurs pour avoir la structure la plus efficace possible;
et de permettre un ajout ou une suppression d'éléments (à la fin par exemple) en temps constant.

Il s'agit donc d'une structure de données concrète souple, implémentant à la fois les types abstraits «liste» et «tableaux».

Elle s'appuie sur la structure concrète de tableau . Un tableau dynamique consiste en :

un tableau t de taille nmax
un indice imax, compris entre -1 et nmax-1

Les données contenues dans un tel tableau dynamique sont simplement les données contenues dans le tableau entre les indices 0 et imax (avec la convention que le tableau dynamique est vide si imax vaut $-1$).

Il y a donc une différence entre la taille du tableau dynamique (imax+1, i.e. le nombre d'éléments qu'il contient) et sa capacité (nmax, i.e. le nombre maximal d'éléments qu'il pourra contenir sans réallocation de mémoire).

L'accès à un élément du tableau dynamique s'effectue donc en temps constant, puisqu'il s'agit d'un accès à un élément d'un tableau.

Tant que imax < nmax-1, l'insertion à la fin s'effectue également en temps constant : il suffit d'incrémenter imax, puis de mettre la donnée voulue dans la case d'indice imax. L'insertion de «1» en fin du tableau précédent donnera donc le tableau suivant :

Si l'on souhaite supprimer un élément à la fin, il suffit de décrémenter imax. La donnée stockée dans la case correspondant à l'ancienne valeur d'imax n'a plus d'importante, et sera écrasée lors d'une prochaine insertion d'élément à la fin.

Que faire maintenant si l'on souhaite ajouter un élément à la fin du tableau dynamique suivant ?

Il va falloir réallouer de la mémoire, et recopier le tableau actuel - cf la section sur les tableaux. Ces opérations prenant du temps on va tant qu'à faire allouer plus de mémoire que ce qui serait nécessaire pour simplement ajouter un élément : on prévoit une marge, qui permettra de faire en sorte de ne pas avoir à faire de réallocation lors des prochains ajouts. Classiquement, on se donne un paramètre $\mathbf{a>1}$ et on réserve un espace mémoire permettant de stocker un tableau de taille $an_{max}$ (arrondi à un entier), où $n_{max}$ est la capacité du tableau actuel. Un cas typique est $a=2$ : la capacité du tableau va doubler lorsqu'on a besoin de faire une réallocation, et l'on obtiendra par exemple le tableau suivant - obtenu par ajout de «3» à la fin du tableau précédent :

Ajout de e à la fin d'un tableau dynamique de paramètre $\mathbf{a= 2}$

Si la taille est strictement inférieur à la capacité :
- imax ← imax+1
- t[imax] ← e
Sinon :
- Réallouer en mémoire un tableau de taille a*imax (arrondi à l'entier supérieur), y recopier le contenu de t et faire pointer t dessus
- imax ← imax+1
- t[imax] ← e

Considérons un tableau dynamique initialement de capacité 1, avec $a=2$, et supposons qu'on lui ajoute successivement $n>1$ éléments. Des réallocations vont avoir lieu lors des ajouts $1, 2, 4, 8\dots $ (voir le schéma ci-dessous) jusqu'à la plus grande puissance de 2 inférieure à $n$ - i.e. $2^{\lfloor \log_2(n)\rfloor}$. Si l'on considère que la réallocation se fait en temps proportionnel à la taille du tableau, le temps de réallocation au bout des $n$ ajouts sera de l'ordre de $O\left(\sum_{j=1}^{\lfloor \log_2(n)\rfloor}2^j\right)$ dont un simple calcul montre qu'il s'agit d'un $O(n)$. En moyenne, un ajout coûte donc $O\left(\frac{n}{n}\right)=O(1)$. On parle de complexité amortie constante - même si l'on n'a pas la garantie qu'un ajout donné soit effectué en temps constant.

Les tableaux dynamiques ont un surcoût en mémoire - mesuré par leur taux de remplissage, i.e. le rapport entre leur taille et leur capacité. Tant que l'on ne fait qu'ajouter des éléments, ce taux de remplissage est supérieur à $\frac{1}{a}$. Ce n'est plus nécessairement le cas lorsque qu'on enlève des éléments avec la stratégie décrite ci-dessus. Pour y remédier, on peut décider d'effectuer une réallocation réduisant la taille du tableau lorsque le taux de remplissage devient inférieur à une certaine valeur. Il est souhaitable que cette nouvelle opération de réallocation ait également un coût amorti constant, quelle que soit la séquence d'ajouts/suppressions effectuée sur le tableau dynamique. Cela peut se garantir, par exemple par la stratégie suivante :

Suppresion à la fin d'un tableau dynamique de paramètre $\mathbf{a}$
On se donne un paramètre $b\leq 1$ tel que $ab<1$.

Si le taux de remplissage est supérieur à $b$
- imax ← imax-1
Sinon :
- Réallouer en mémoire un tableau de taille $ab\times$la taille actuelle, y recopier le contenu de t et faire pointer t dessus
- imax ← imax-1

L'application ci-dessous permet de développer une intuition des coûts des opérations pour des tableaux dynamiques de paramètres $(a, b)=(2, 1/4)$ et $(a, b)=(5/4, 1/2)$ utilisant la stratégie de suppression décrite ci-dessus. Le coût d'une opération d'insertion ou de suppression est par défaut de 1 - auquel s'ajoute la taille du tableau nouvelle créé si une réallocation est nécessaire.

$\mathbf{a=2,\ b=1/4}$
Coût de la dernière opération :
Coût amorti :
Taux de remplissage :

$\mathbf{a=1.25,\ b=1/2}$
Coût de la dernière opération :
Coût amorti :
Taux de remplissage :

List Python (cf ci-dessous)
Coût de la dernière opération :
Coût amorti :
Taux de remplissage :

Le choix du paramètre $a$ (et également de $b$) résulte d'un compromis entre l'efficacité en terme de nombres d'opérations (qui augmente avec $a$) et l'occupation mémoire (un paramètre $a$ grand implique un surcoût en mémoire plus important).

Il est également possible d'utiliser des heuristiques particulières lorsque le tableau dynamique est petit, pour éviter de faire tout le temps des réallocations (qui en pratique sont des opérations coûteuses - même pour de petits espaces mémoire - dans le sens où la «constante» devant le $O$ est élevée).

	Tableau	Liste simplement chaînée	Liste doublement chaînée	Tableau dynamique
Accès à un élément au début	$O(1)$	$O(1)$	$O(1)$	$O(1)$
Accès à un élément à la fin	$O(1)$	$O(n)$	$O(1)$	$O(1)$
Accès à un élément au milieu	$O(1)$	$O(n)$	$O(n)$	$O(1)$
Ajout d'un élément au début	$O(n)$	$O(1)$	$O(1)$	$O(n)$
Ajout d'un élément à la fin	$O(n)$	$O(n)$	$O(1)$	$O(1)$^*
Suppression d'un élément au début	$O(n)$	$O(1)$	$O(1)$	$O(n)$
Suppression d'un élément à la fin	$O(n)$	$O(n)$	$O(1)$	$O(1)$^*

* Complexité «amortie». Un ajout ou une suppression pris individuellement peut être de complexité $O(n)$

En pratique…

Tour d'horizon de ces différentes structures dans quelques langages.

En Python

En Python, la structure appelée list est (dans l'implémentation de référence CPython) un tableau dynamique, de paramètres $a\approx 1.125$ et $b\approx 0.5$ (avec également un ajout d'un nombre constant de cases de tableau à chaque réallocation, et un cas particulier pour les petits tableaux) - donc très conservatif sur l'espace mémoire lorsque la liste s'agrandit, au détriment de l'efficacité temporelle. Le code source (en C) peut être trouvé sur cette page.
Les complexités temporelles des opérations sur les lists sont bien celles attendues pour un tableau dynamique :

Accès direct en temps constant.
Ajout et suppression à la fin (à l'aide de .append et .pop) en temps amorti constant.
Ajout et suppression au début en temps linéaire en la taille de la liste.

De plus, une liste peut contenir des objets de types différents : cela semble contradictoire avec la contrainte que chaque élément d'une tableau soit codé sur le même nombre de bits, mais s'explique car une liste Python stocke en fait des références vers les objets, et non pas les objets eux-mêmes.
Il s'agit donc d'une structure extrèmement souple (mais qui n'est pas la plus efficace si l'on a simplement besoin d'une implémentation du type de données abstrait «tableau», cf ci-dessous).

À noter que la norme Python ne garantit pas la complexité des opérations sur les lists. Un interpréteur autre que CPython pourrait implémenter les lists différemment, et donc obtenir des performances différentes…

En numpy

Les numpy.array sont une implémentation du type abstrait «tableau». Ils sont à cet égard d'une très grand efficacité et sont utilisés de préférentiellement aux listes Python en calcul numérique et simulation.
numpy dispose d'une fonction append, qui ne se comporte pas du tout comme le .append des listes Python. En particulier, elle effectue une copie du tableau passé en argument. Si vous avez besoin d'une implémentation du type abstrait «liste» - par exemple parceque votre code ajoute tout le temps des éléments en fin de liste, vous ne voulez probablement pas utiliser les numpy.array.

deque

Les deque Python sont des listes doublement chaînées - implémentant donc le type de données abstrait «liste», mais pas le type de données abstraite «tableau».

En C++

Tout comme en C les tableaux sont en C++ une structure de base, que le programmeur gère directement via des (ré-)allocations de mémoire. Cela laisse une souplesse maximale, mais demande plus de temps de développement, et implique plus de responsabilités, par exemple pour éviter les «fuites de mémoire»…

Les vectors sont une structure de tableau dynamique, avec un paramètre $a=2$. En revanche, lors d'une suppression à la fin d'un vecteur (à l'aide de pop_back), il n'y a jamais de réallocation : la capacité du vecteur n'est pas modifiée. On peut néanmoins manuellement ramener à la capacité à la taille du vecteur en utilisant la commande shrink_to_fit().

En OCaml

Les listes chaînées sont centrales en OCaml. Elles se notent avec des crochets (e.g. [1; 2; 3]), et l'apprentissage de base de ce langage tourne complètement autour de cette structure.
Les tableaux existent également, et se notent [|1; 2; 3|].

Références

Algorithmique, de Cormen et al.
La complexité temporelle des opérations sur les «listes» en Python
Le code C implémentant les «listes» Python