Modèle de données “liste”

On appelle liste d'éléments d'un ensemble \(E\) toute séquence \((L_i)_{i\in I}\) d'éléments de \(E\), sa longueur désigne simplement le nombre de ses termes. Si une liste est de longueur \(n\in\N\) et sans précisions particulières, son ensemble d'indexation est supposé être l'intervalle \({\ab{1}{n}}\) défini sur l'ensemble des entiers naturels \({\N}\) pour l'ordre naturel. Ce sera parfois l'intervalle \(\ab{0}{n-1}\) qui sera utilisé par souci de simplification (ce qui correspond à la convention généralement adoptée dans la plupart des langages de programmation) mais dans ce cas nous le préciserons.

Il peut paraître redondant de définir un objet déjà présent dans l'arsenal mathématique, mais les spé­ci­fi­ci­tés des structures associées et l'usage immodéré des listes en algorithmique justifient une étude à part entière.

Du point de vue des notations, on préfère l'écriture \(L[i]\) à \(L_i\) pour désigner le terme d'index \(i\in I\) de la liste \(L\). On décrit souvent une liste avec son écriture en extension, c'est-à-dire à partir des termes qui la constituent, par exemple : \begin{equation}\label{eq:ex} L=[l,i,s,t,e,e,n,e,x,t,e,n,s,i,o,n] \end{equation}

Le vocabulaire des suites et des séquences s'applique naturellement pour les listes. Soit \(a\) et \(b\) deux éléments de l'ensemble d'indexation \(I\) tels que \(a\leq b\), on note \(L[a\!:\!b]\) la sous-liste constituée des éléments d'index \(a\) à \(b\) (inclus) de la liste \(L\). Par exemple, si l'ensemble d'indexation de la liste définie en (\(\ref{eq:ex}\)) est \(I=\ab{1}{16}\), alors \[L[4\!:\!7]=[t,e,e,n].\] On note \([\;]\) la liste vide.

Ce sont les opérations que l'on peut effectuer sur les listes qui rendent ce modèle si versatile, re­cher­che, insertion, suppression d'un élément, entre autres. La concaténation de deux listes \(A\) et \(B\) que l'on note \(A.B\), est constituée des termes de la liste \(A\) suivie des termes de la liste \(B\), ainsi \[[1,2,3].[4,5]=[1,2,3,4,5].\] C'est une loi de composition interne sur les listes sur un même ensemble \(E\). Elle est associative et la liste vide \([\;]\) joue le rôle d'élément neutre, i.e. si \(L\) est une liste \(L.[\;]=[\;].L=L\). Elle n'est bien sûr pas commutative. À l'instar des ensem­bles, on écrira (abusivement) \(x\in L\) pour signifier que l'élé­ment \(x\) est présent dans la liste \(L\), autre­ment dit qu'il existe au moins un index \(i\in I\) tel que \(L[i]=x\).

Toutes ces opérations formelles fort pratiques, n'indiquent nullement comment elles seront réalisées. Cela dépend essentiellement de la structure de données associée dans un langage de program­ma­tion (ou notre pseudo-langage algorithmique) et c'est là que les difficultés commencent.

Il existe plusieurs déclinaisons structurelles du modèle de données liste, les plus communes étant les listes chaînées, les tuples, les tableaux, les vecteurs ou les chaînes qui elles-même peuvent présenter des spécificités selon le langage de programmation. Ces structures ne recouvrent souvent que de manière partielle le modèle de référence, par exemple l'indexation n'est pas toujours disponible. Con­cep­tuel­le­ment, on peut classer ces structures en deux groupes :

1. Les structures statiques .
2. Les structures dynamiques.

Structures statiques

Les structures statiques peuvent l'être pour plusieurs raisons. Leur taille est généralement spécifiée à l'avance et ne peut évoluer dans le temps. Elle contiennent par conséquent des objets de même nature (type). Parfois les valeurs rangées dans la structure ne sont pas modifiables (tuples ou chaînes dans certains langages). Dans notre modèle algorithmique, les tableaux contiennent des données de même nature mais leur contenu est modifiable.

Comme nous l'avons vu dans l'étude du modèle de la machine ram, la mémoire d'un ordinateur est organisée en table avec un accès direct indexé. Pour ranger \(n\) objets de taille \(\color{#FF0}s\) d'un tableau \(T\) dans une mémoire de ce type, le système d'exploitation va allouer au programme \(n\times s\) registres mémoire contigüs qui débutent à une certaine adresse \(\color{#BBF}a\). Ainsi, l'adresse mémoire du \(i\)-ème terme \(T[i]\) d'une telle structure est obtenue à l'aide d'une simple fonction affine \[i\stackrel{@}{\mapsto} {\color{#FF0}s}i+{\color{#BBF}a}.\] C'est précisément ce mécanisme d'adressage direct qui caractérise les ordinateurs de type ram. C'est cette structure qui est la plus proche de la définition abstraite d'une liste.

La façon dont les systèmes d'exploitation gèrent les allocations mémoire ne permet pas de réaliser nombre d'opérations importantes sur les listes sans rompre ce mécanisme d'indexation. Rajouter des éléments à une liste suppose que les nouveaux registres alloués par le système se situent à la suite du dernier registre mémoire associé à cette liste, ce qui n'est pas nécessairement possible. La con­ca­té­na­tion de deux listes \(L.M\) pose le même problème, il est fort peu probable que le dernier registre alloué pour la liste \(L\) soit justement celui qui précède le premier registre alloué pour la liste \(M\). Dans ce dernier cas, la conséquence est fâcheuse, il faut demander au système d'allouer \(s(|L|+|M|)\) registres pour y ranger les éléments des deux listes \(L\) et \(M\), faire la copie puis libérer l'espace mémoire occupé par ces listes avant la concaténation. Ceci peut s'avérer rédhibitoire pour certains algorithmes.

Structures dynamiques

De nombreuses opérations fondamentales sur les listes sont difficiles à réaliser avec les structures statiques, il est donc nécessaire de développer d'autres structures pour lesquelles ces opérations se font simplement, au moins pour le programmeur. C'est donc principalement parce que leur taille et leur contenu peut varier durant l'exécution d'un programme que certaines structures associées aux listes sont qualifiées de dynamiques. Le sous-entendu est que ces variations se font sans coût excessif. Avant même d'aborder les opérations classiques sur les listes, il faut réaliser que si les deux types de structures coexistent c'est qu'aucune ne permet de réaliser l'intégralité des opérations usuelles efficacement. La nature de l'algorithme conduira à privilégier l'une ou l'autre.

Une façon classique d'obtenir une structure de liste dynamique est de créer une liste chaînée. Pour chaque élément \(L[i]\) de la liste, le système alloue un bloc mémoire appelé enregistrement, qui permet de ranger à la fois l'élément \(L[i]\) de la liste et l'adresse (appelée pointeur) du prochain en­re­gis­tre­ment. Un pointeur particulier, le pointeur vide, permet de terminer le processus de chaî­nage. Dans la figure suivante, un enregistrement est représenté par une boite contenant :

1. Un terme de la liste,
2. Un pointeur matérialisé par un bloc de couleur et une flèche à droite → (un bloc rouge pour désigner le pointeur vide).

On a ici un adressage séquentiel, autrement dit pour atteindre un élément particulier, il est né­ces­sai­re de parcourir les enregistrements de la liste les uns après les autres depuis la tête de la liste en suivant le chainage.

Une autre structure est également largement utilisée, la liste doublement chaînée. Le principe est le même que pour une liste chaînée, mais on range deux pointeurs dans l'enregistrement, un vers l'enregistrement suivant, un vers le précédent. Ce chaînage est circulaire, le dernier pointeur pointe vers le premier enregistrement et le premier vers le dernier.

Le coût en mémoire de ces deux structures est important puisque les adresses utilisent un registre mémoire, donc 8 octets sur un processeur 64 bits par exemple. Nous allons voir que ce surcoût a néanmoins des contreparties en terme de complexité en temps pour nombre d'opérations fon­damen­tales sur les listes.

Opérations sur les listes

Calcul de la longueur

Recherche d'un élément

Insertion d'un élément

Pour une structure de tableau, l'insertion d'un élément \(x\) à la position \(i\) dans un tableau de taille \(n\) se fait au prix de la création d'un nouveau tableau de taille \(n+1\) et de la copie des éléments du tableau initial aux autres positions. La complexité est donc \(\Theta(n)\). Dans le cas d'une liste chaînée ou doublement chaînée, le pointeur vers l'enregistrement remplace l'index où doit se faire l'insertion et cette opération se fait tout simplement en créant un enregistrement contenant \(x\) et en modifiant le chaînage. Le pointeur qui reliait \(c\) à \(d\) est détaché puis pointé sur \(x\), et le pointeur de \(x\) est dirigé sur \(d\) :

La méthode est similaire dans le cas d'une liste doublement chaînée, il faut simplement gérer deux pointeurs au lieu d'un. Le coût d'une insertion se fait donc en temps constant \(\Theta(1)\). Les positions initiales et finales jouent évidemment un rôle particulier pour l'insertion, notamment dans les files et les piles que nous étudierons plus loin. Si l'insertion se fait en tête de liste, le pointeur est connu dans les deux cas, que la liste soit simplement ou doublement chaînée. En revanche, si l'insertion doit se faire en fin de liste, il faut parcourir toute la liste simplement chaînée pour déterminer ce pointeur ce qui a un coût linéaire \(\Theta(n)\) alors que ce coût est constant pour une liste doublement chaînée. Il est possible néanmoins d'avoir de réaliser une insertion aec coût constant pour une liste simplement chaînée, il suffit de conserver un pointeur vers le dernier enregistrement (en copiant la valeur du pointeur vers l'enregristrement contenant \(e\) dans l'exemple ci-dessus).

Suppression d'un élément

Dans le cas d'une liste chaînée ou doublement chaînée, il faut simplement modifier le chaînage et restituer la mémoire contenant l'enregistrement à supprimer. Le procédé est illustré ci-dessous avec la suppression de l'élément \(c\) de la liste \(L=[a,b,c,d,e]\). Le pointeur qui reliait \(b\) à \(c\) est redirigé vers \(d\) et l'enregistrement contenant \(c\) est restitué au système. Il faut donc créer un pointeur vers \(c\) avant d'opérer la déviation, référence indispensable pour effectuer cette restitution.

Concaténation de deux listes

Dans le cas de deux tableaux \(T\) et \(S\) de tailles respectives \(n\) et \(m\), il faut allouer un tableau de taille \(n+m\) et y copier successivement tous les éléments de \(T\) puis de \(S\). Le coût est donc en \(\Theta(n+m)\). Pour deux listes chaînées \(L\) et \(M\), il suffit de modifier le pointeur d'enregistrement suivant (pointeur vide) en queue de liste \(L\) pour le pointer vers le début de la liste \(M\). Néanmoins, comme pour l'insertion et la suppression, il faut trouver le pointeur suivant du dernier enregistrement de la liste \(L\) ce qui a un coût \(\Theta(n\)) alors que s'il s'agit d'une liste doublement chaînée ce pointeur est connu et la concaténation se fait en \(\Theta(1)\). Il faut également faire pointer le pointeur précédent du premier enregistrement de la liste \(M\) vers le dernier enregistrement de la liste \(L\).

Les files et les piles

Les files et les piles sont omniprésentes en informatique et interviennent dans une multitude d'algo­ri­thmes. Nous avons rencontré les files dans le chapitre Tri par dénombrement et par répartition et nous utiliserons une pile dans le chapitre Évaluation d'une expression. Nous verrons en troisième année dans le chapitre consacré à la récursivité que c'est grâce à une pile que l'on peut développer des langages récursifs.

Struc­turel­lement, les files et les piles ne sont que des listes, ce sont les opérations d'insertion et de suppression d'un élément que l'on autorise sur la structure qui confèrent à une liste son statut de file ou de pile. Ces deux opérations se font dans les deux cas uniquement au début et/ou à la fin de la liste, l'indexation des termes de la liste est donc par nature secondaire. Cette limitation et l'aspect dynamique des opérations d'insertion et de suppression font que les structures dynamiques de listes chaînées ou doublement chaînées sont naturellement privilégiées par rapport aux tableaux. Précisons que dans de nombreux langages de programmation, la manière dont sont implantées les listes est transparente pour le programmeur, l'objet de ce chapitre est de mettre en évidence l'impact du choix de la mise en œuvre en terme de complexité et de lui permettre de choisir la meilleure structure si un choix est possible ou s'il a connaissance de la structure sous-jacente utilisée.

Une file est une liste pour laquelle les opérations d'insertion et de suppression se font aux extrémités opposées de la liste, bien que l'usage général soit d'insérer un nouvel élément en fin de liste et la suppression en début de liste, le sens étant fixé par l'indexation quand il s'agit d'une structure de tableau ou par les pointeurs de la liste chaînée quand ils sont vus comme des flèches. Il s'agit du même concept que celui de file d'attente, le premier entré est le premier sorti (les anglo-saxons désignent pragmatiquement les files par l'acronyme fifo pour First In First Out). Ainsi, dans une file, on appelle tête, la position (ou le pointeur) au début de la file et queue la position (ou le pointeur) à la fin de la file. Dans une pile, on appelle sommet, la position (ou le pointeur) où se fait l'insertion et la suppression. La position opposée des opérations d'insertion et de suppression poussent généralement à utiliser une structure doublement chaînée.

Une pile est une liste pour laquelle les opérations d'insertion et de suppression se font aux mêmes extrémités de la liste. Il s'agit du même concept que celui de pile d'assiettes, la dernière assiette est placée au sommet de la pile, le dernier entré est le premier sorti (les anglo-saxons désignent toujours aussi pragmatiquement les piles par l'acronyme lifo pour Last In First Out). Dans une pile, on appelle base, la position ou le pointeur au début de la pile et sommet la position ou le pointeur à la fin de la pile. Les piles sont souvent implantées sous forme de listes simplement chaînées puisque les deux opérations se font à la même extrémité, et dans ce cas l'insertion et la suppression se font en \(\Theta(1)\) sur le début de la liste si l'on se réfère à la figure 1, dans ce cas le sommet de la pile désigne bien sûr le début de la liste.

Dans tout le cours, nous utiliserons librement les algorithmes :

• Enfiler(F,x) qui enfile (rajoute) l'élément \(x\) au bout de la file \(F\) ;
• Défiler(F) qui défile (supprime) le dernier élément de la file \(F\) et le renvoie  ;
• Empiler(P,x) qui empile (rajoute) l'élément \(x\) au sommet de la pile \(P\) ;
• Dépiler(P) qui dépile (supprime) l'élément au sommet de la pile \(P\) et le renvoie.
• Tête(L) qui renvoie l'élément en tête de la liste \(L\), sans modifier la liste.
• Queue(L) qui renvoie l'élément en queue de la liste \(L\), sans modifier la liste.