Les listes chaînées
1. Listes chaînées simples
a. Principe
Dans la vie quotidienne, une liste revêt plusieurs formes : une liste de courses, de tâches à effectuer, un index, un
glossaire, une collection de dvds, de musiques, etc. Ces listes sont composées d’éléments individuels, liés les uns aux
autres par leur type ou l’ordre que vous voulez leur donner. Pour passer d’un élément à un autre, vous descendez
dans la liste dans l’ordre que vous lui avez donné.
Comment se représenter une liste, par définition linéaire, en programmation ? Vous connaissez au moins un moyen :
les tableaux. Dans un tableau, vous pouvez y stocker n éléments, et l’ordre peut être représenté par l’indice du
tableau.
Connaissezvous un autre moyen de stocker des éléments ? Les enregistrements de types structurés le permettent,
et en plus vous pouvez y stocker bien plus de détails. Vous pouvez aussi créer des tableaux d’enregistrements, donc
leur donner un certain ordre.
L’utilisation des tableaux pose cependant parfois des problèmes un peu complexes. Vous l’avez déjà remarqué avec
les méthodes de tris.
q Comment insérer un nouvel enregistrement en début de tableau ? Il n’y a pas d’indices négatifs…
q Comment insérer un nouvel enregistrement en fin de tableau ? Si l’algorithmique propose un
redimensionnement dynamique, les langages comme Java ne le permettent pas.
q Comment insérer un élément au milieu du tableau ? Fautil décaler tous les éléments pour placer le nouveau
à l’endroit donné ? Si oui, le tableau risque de déborder.
q Et si vous supprimez un enregistrement, allezvous de nouveau décaler le tableau pour boucher le trou ? Ou
trouver une parade pour passer pardessus ?
Vous pouvez vous arranger pour tout programmer afin de tout faire marcher avec les tableaux. C’est parfaitement
possible. Mais estce vraiment raisonnable ? Estce de la programmation efficace ? Rappelezvous qu’au chapitre
Introduction à l’algorithmique vous avez appris qu’il faut être économe en ressources. Cette méthode est gourmande
et compliquée. Il vous faut en trouver une autre plus simple et plus belle.
En fait, encore une fois, vous connaissez tous les principes de base de cette nouvelle méthode. Voici quelques
éléments :
q Un enregistrement peut contenir un autre enregistrement.
q Cet autre enregistrement peut être du même type structuré.
q L’enregistrement peut aussi contenir un pointeur vers un autre enregistrement du même type.
q En notation Java, un enregistrement est un objet, et dans un objet, on peut référencer un autre objet du
même type.
q On obtient, du coup, une cascade d’enregistrements qui se suivent les uns les autres. Pour accéder au
suivant, il suffit d’accéder à la référence de cet enregistrement dans l’enregistrement actuel.
q Chaque enregistrement dispose d’un pointeur ou référence vers le suivant.
q Les enregistrements sont donc chaînés les uns aux autres, c’est une liste chaînée d’enregistrements.
Le principe peut être représenté par le schéma suivant. Chaque enregistrement est représenté par un cadre et
contient une valeur et un pointeur appelé psuiv qui pointe sur l’enregistrement suivant de la liste.
- 1 -
© ENI Editions - All rigths reserved - Jonifar lina
174
1. Listes chaînées simples
a. Principe
Dans la vie quotidienne, une liste revêt plusieurs formes : une liste de courses, de tâches à effectuer, un index, un
glossaire, une collection de dvds, de musiques, etc. Ces listes sont composées d’éléments individuels, liés les uns aux
autres par leur type ou l’ordre que vous voulez leur donner. Pour passer d’un élément à un autre, vous descendez
dans la liste dans l’ordre que vous lui avez donné.
Comment se représenter une liste, par définition linéaire, en programmation ? Vous connaissez au moins un moyen :
les tableaux. Dans un tableau, vous pouvez y stocker n éléments, et l’ordre peut être représenté par l’indice du
tableau.
Connaissezvous un autre moyen de stocker des éléments ? Les enregistrements de types structurés le permettent,
et en plus vous pouvez y stocker bien plus de détails. Vous pouvez aussi créer des tableaux d’enregistrements, donc
leur donner un certain ordre.
L’utilisation des tableaux pose cependant parfois des problèmes un peu complexes. Vous l’avez déjà remarqué avec
les méthodes de tris.
q Comment insérer un nouvel enregistrement en début de tableau ? Il n’y a pas d’indices négatifs…
q Comment insérer un nouvel enregistrement en fin de tableau ? Si l’algorithmique propose un
redimensionnement dynamique, les langages comme Java ne le permettent pas.
q Comment insérer un élément au milieu du tableau ? Fautil décaler tous les éléments pour placer le nouveau
à l’endroit donné ? Si oui, le tableau risque de déborder.
q Et si vous supprimez un enregistrement, allezvous de nouveau décaler le tableau pour boucher le trou ? Ou
trouver une parade pour passer pardessus ?
Vous pouvez vous arranger pour tout programmer afin de tout faire marcher avec les tableaux. C’est parfaitement
possible. Mais estce vraiment raisonnable ? Estce de la programmation efficace ? Rappelezvous qu’au chapitre
Introduction à l’algorithmique vous avez appris qu’il faut être économe en ressources. Cette méthode est gourmande
et compliquée. Il vous faut en trouver une autre plus simple et plus belle.
En fait, encore une fois, vous connaissez tous les principes de base de cette nouvelle méthode. Voici quelques
éléments :
q Un enregistrement peut contenir un autre enregistrement.
q Cet autre enregistrement peut être du même type structuré.
q L’enregistrement peut aussi contenir un pointeur vers un autre enregistrement du même type.
q En notation Java, un enregistrement est un objet, et dans un objet, on peut référencer un autre objet du
même type.
q On obtient, du coup, une cascade d’enregistrements qui se suivent les uns les autres. Pour accéder au
suivant, il suffit d’accéder à la référence de cet enregistrement dans l’enregistrement actuel.
q Chaque enregistrement dispose d’un pointeur ou référence vers le suivant.
q Les enregistrements sont donc chaînés les uns aux autres, c’est une liste chaînée d’enregistrements.
Le principe peut être représenté par le schéma suivant. Chaque enregistrement est représenté par un cadre et
contient une valeur et un pointeur appelé psuiv qui pointe sur l’enregistrement suivant de la liste.
- 1 -
© ENI Editions - All rigths reserved - Jonifar lina
174