Algorithmique ii - Modèle et structures de données liste

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{\mathbf N}\) et sans précisions particulières, son ensemble d'indexation est supposé être l'intervalle \([1,n]\) défini sur l'ensemble des entiers naturels \({\mathbf N}\) pour l'ordre naturel. Ce sera parfois l'intervalle \([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. Soient \(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=[1,16]\), alors \[L[4\!:\!7]=[t,e,e,n].\] On note \([\;]\) la liste vide.

Le langage Python utilise la même notation crochets mais exclut l'élément d'indice \(b\). Les raisons de ce choix sont nébuleuses et ne sont pas con­vain­quan­tes mais ne sont pas plus ésotériques que celles qui justifient l'usage du sym­bo­le d'égalité pour coder l'affectation…

Les notations utilisées pour les intervalles en mathématiques, comme les ouverts \(]a,b[\) ou semi-ouverts \([a,b[\) et \(]a,b]\), ne sont pas implantés en Python en raison des problèmes d'ana­ly­se syn­ta­xi­que qu'ils pourraient créer (le crochet droit de l'intervalle semi-ouvert \([a,b[\), ferme-t-il l'in­ter­val­le ou indique t-il l'ouverture d'un nouvel intervalle ?).

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 eux-mêmes 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.
Dans tout le cours, quand nous ferons référence à un tableau il s'agira d'une structure statique et nous réserverons le terme de liste aux structures dynamiques. La nature statique ou dynamique est intimement liée à la gestion de la mémoire sans que cette différence ne soit nécessairement mise en évidence dans les langages de programmation qui fournissent cette structure dans leur arsenal. La connaissance des mécanismes sous-jacents est fondamentale pour évaluer la complexité des algo­rith­mes qui manipulent ces structures. On trouvera dans ce document réalisé par Richard E. Pattis, la complexité des différentes opérations possibles sur les listes du langage Python.

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 la 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.

On se donne une mémoire de \(n\) registres contigüs initialement libres. On demande au système une première allocation de \(k\) registres contigüs puis une seconde allocation de \(l\) registres contigüs avec \(k+l\leq n\). En supposant que le système choisisse l'adresse du premier registre de chacun des deux blocs au hasard, calculez la probabilité que l'adresse du premier registre du second bloc soit égale à l'adresse qui suit celle du dernier registre du premier bloc.
L'adressage indirect permet de ranger des données hétérogènes dans un tableau \(T\) (sa taille reste néanmoins fixe). On alloue la mémoire pour ranger \(n\) pointeurs, c'est-à-dire \(n\) adresses dont la taille est fixe et qui pointent vers les données à ranger. Ainsi \(T[i]\) ne contient pas la donnée directement mais son adresse mémoire qui permet d'y accéder.

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.

\(L\)\(\rightarrow\) a\(\color{#FF0}\longrightarrow\) b\(\color{#FF0}\longrightarrow\) c\(\color{#FF0}\longrightarrow\) d\(\color{#FF0}\longrightarrow\) e
Liste chaînée associée à la liste \(L=[a,b,c,d,e]\).

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.

\(L\downarrow\)
vers \(e\) \(\color{#BB0}\curvearrowleft\) a \(\stackrel{\color{#FF0}\longrightarrow}{\color{#BB0}\longleftarrow}\) b \(\stackrel{\color{#FF0}\longrightarrow}{\color{#BB0}\longleftarrow}\) c \(\stackrel{\color{#FF0}\longrightarrow}{\color{#BB0}\longleftarrow}\) d \(\stackrel{\color{#FF0}\longrightarrow}{\color{#BB0}\longleftarrow}\) e \(\color{#FF0}\curvearrowright\)vers \(a\)
Liste doublement chaînée associée à la liste \(L=[a,b,c,d,e]\).

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

Dans le cas d'un tableau, la taille du tableau est connue par construction, le coût est nécessairement constant. Dans le cas d'une liste chaînée ou doublement chaînée, on pourrait penser qu'il est nécessaire de parcourir toute la liste pour en déterminer le nombre, mais l'information est tellement importante qu'elle est en général rangée dans un enregistrement contenant également le pointeur de liste. Dans les deux cas le coût est donc \(\Theta(1)\).

Recherche d'un élément

Quelle que soit la structure choisie, la recherche d'un élément \(x\) dans une liste \(L\) demande de parcourir la liste pour renvoyer la position \(i\) de l'élément pour un tableau ou le pointeur dans le cas d'une liste chaînée ou doublement chaînée. Dans le pire des cas, c'est-à-dire si l'élément n'est pas présent dans la liste, la complexité est linéaire en \(\Theta(n)\). Aucune des deux structures n'a donc l'avantage sur l'autre bien que la structure indexée est en réalité plus rapide pour une même complexité linéaire.

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\) :

\(L\)\(\rightarrow\) a\(\color{#FF0}\longrightarrow\) b\(\color{#FF0}\longrightarrow\) c\(\color{#FF0}\longrightarrow\) d\(\color{#FF0}\longrightarrow\) e
 
\(L\)\(\rightarrow\) a\(\color{#FF0}\longrightarrow\) b\(\color{#FF0}\longrightarrow\) c d\(\color{#FF0}\longrightarrow\) e
  \(\quad\color{#AAF}\searrow\) \(\color{#AFA}\nearrow\quad\)
x
Insertion de l'élément \(x\) à la place de \(d\) dans la liste chaînée \(L=[a,b,c,d,e]\).

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'un tableau \(T\) de taille \(n\), si on doit éliminer l'élément à la position \(i\), il faut allouer un nouveau tableau de taille \(n-1\) et faire la copie de tous les éléments de \(L\) sauf celui d'indice \(i\). On peut dans certains cas éviter la création d'un nouveau tableau en décalant tous les termes qui suivent l'élément d'indice \(i\) d'une position vers la gauche \[T[k]\leftarrow T[k+1]\] pour \(k\in[i,n-1]\), le dernier terme du tableau étant alors perdu. Dans les deux cas la complexité dans le pire des cas est en \(\Theta(n)\).

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.

\(L\)\(\rightarrow\) a\(\color{#FF0}\longrightarrow\) b\(\color{#FF0}\longrightarrow\) c\(\color{#FF0}\longrightarrow\) d\(\color{#FF0}\longrightarrow\) e
 
vers \(d\)
  \(\color{#AAF}\nearrow\) \(\color{#AAF}\searrow\)
\(L\) a\(\color{#FF0}\longrightarrow\) b c d\(\color{#FF0}\longrightarrow\) e
\(\color{#AA4}\nearrow\)
Suppression de l'élément \(c\) dans la liste chaînée \(L=[a,b,c,d,e]\).
L'opération de suppression a donc elle aussi un coût constant \(\Theta(1)\). Comme pour l'insertion d'un nouvel élément, il faut connaître le pointeur vers l'enregistrement à supprimer.

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ées 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, rien ne distinque une file ou une pile d'une liste, ce sont les opérations d'insertion et de suppression d'un élément que l'on autorise sur la structure qui leur confère leur statut. Ces deux opérations se feront 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. 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). 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. 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 :

Écrivez les fonctions qui correspondent aux quatre algorithmes Enfiler(F,x), Défiler(F), Empiler(P,x) et Dépiler(P) en langage C à l'aide de listes chaînées pour les piles et de listes doublement chaînées pour les files.