Listes chaînées
Listes simplement chaînées
Toutes les structures que nous avons vues jusqu'à présent ont plusieurs problèmes en commun : il faut toujours à l'avance fixer un nombre maximum d'éléments, et il est toujours extrêmement difficile d'insérer ou de supprimer un élément n'importe où dans la liste.
On peut remarquer que ce problème vient du simple fait qu'avec un tableau, il faut toujours avoir, quelque part, un emplacement continu de mémoire dont la taille dépend du nombre d'éléments maximal. Mais rien ne nous oblige à utiliser un tableau. C'est ainsi que l'on va créer le premier jeu de piste dont le joueur est un ordinateur.
L'idée est la suivante : ne retenons pas « quelque part » l'ensemble des adresses de tous les éléments. A l'inverse, on va juste en retenir 1 : le premier élément. On se sera également débrouillé pour que quelque part sur ce premier élément se trouve une information qui représente l'adresse du deuxième élément. Si ce deuxième élément pointe à son tour vers le troisième, qui pointe vers le quatrième, et ainsi de suite, le problème est réglé.
Pour ce faire, il faut donc que chaque élément contient deux informations : la donnée effectivement présente à cet endroit (ou un pointeur vers cette donnée, cette seconde approche sera utilisée ici), et un pointeur vers l'élément suivant. On verra donc apparaître une structure du style :
| C | Pascal |
|---|---|
struct item
{
void* data;
item* next;
}
|
Type
PItem=^TItem;
TItem=Record
Data:Pointer;
Next:PItem;
End;
|
En général, le tout premier élément, appelé la tête (head), ne contient pas vraiment de données, mais est juste là pour, justement, servir de tête de liste. Le premier élément sera en réalité l'élément pointé par le champ next de la tête. Le second élément sera l'élément pointé par le champ next du premier élément, etc... On fait comme ça pour permettre la gestion aisée de file vides.
Sur un chtit dessin, ça donne ceci :
Head est donc, finalement, la seule variable présente dans notre programme, vu qu'à partir de cette tête, on peut atteindre de proche en proche tous les autres éléments de la liste.
| C | Pascal |
|---|---|
item Head;
|
Var head:TItem;
|
Il est très simple de rajouter un élément au début de la liste, donc juste après Head, vu qu'il suffit de modifier le champ next de head vers le nouvel élément, et de faire pointer le champ next de notre nouvel élément vers l'élément précédemment pointé par Head :
Retirer un élément ne pose pas plus de problème, vu qu'il suffit de faire pointer le champ next de la tête vers le champ next du premier élément, c'est à dire vers le champ next du champ next de la tête :
| C | Pascal |
|---|---|
Head.Next=Head.Next->Next;
|
Head.Next:=Head.Next^.Next;
|
Par contre, rajouter ou supprimer des éléments ailleurs dans la file n'est pas forcément une chose aisée, car si on veut supprimer l'élément 1, par exemple, il va falloir être capable de modifier le champ Next de élément 2 pour qu'il pointe vers élément 0. Or, même si on connaît l'adresse de l'élément 1 via un pointeur quelconque, il n'est pas possible d'en déduire un pointeur vers l'élément précédent. C'est ainsi que l'on a développé un concept plus complet.
Listes doublement chaînées
La liste doublement chaînée n'est que la généralisation de la liste simplement chaînée : en plus de l'élément suivant, chaque élément possède un pointeur vers l'élément qui le précède.
| C | Pascal |
|---|---|
struct item
{
void* data;
item* next;
item* prev;
}
|
Type
PItem=^TItem;
TItem=Record
Data:Pointer;
Next:PItem;
Prev:PItem;
End;
|
Cette fois-ci, nous garderons deux éléments « spéciaux » au lieu d'un seul : à nouveau la tête, mais nous y rajoutons la queue (tail). Je refais mon petit dessin :
Cette fois-ci, ajouter un élément n'importe où dans la file devient très simple, pour autant que l'on connaisse un pointeur vers l'élément avant ou après lequel on désire l'insérer. Par exemple, pour insérer un élément entre les deux éléments de la file, il faut que :
- Le champ next de l'élément 0 pointe vers notre nouvel élément
- Le champ prev de l'élément 1 pointe vers notre nouvel élément
- Le champ next du nouvel élément pointe vers l'élément 1
- Le champ prev du nouvel élément pointe vers l'élément 0
Retirer un élément est tout aussi facile, à vous de trouver comment faire...
Avec ce nouveau système, il est très facile de modifier la composition de la liste. Par contre, il est difficile d'atteindre directement un élément quelconque : si on nous demande l'élément 148 d'une liste, on va être obligé de parcourir élément par élément, les 147 premiers éléments de la file avant d'atteindre notre destination. C'est le prix à payer.