Représentation logique d’une liste chaînée
Pour accéder à un élément donné de la liste vous partez toujours du premier élément. De là connaissant l’adresse du
suivant par le pointeur psuiv, vous passez successivement aux n suivants. Quand le pointeur ne pointe sur plus rien
(null), c’est que l’enregistrement est le dernier.
Une liste chaînée de ce type est dite unilatère : l’accès aux éléments composant la liste est séquentiel (vous devez
lire les n éléments précédents pour accéder à celui voulu), et unidirectionnel.
Chaque élément de la liste est un enregistrement. Cet enregistrement peut contenir autant de champs que vous le
souhaitez, mais l’un d’eux sera un pointeur sur un enregistrement de même type. Quand vous rajouterez un
deuxième élément, vous placerez son adresse dans le pointeur du premier, et ainsi de suite. Chaque enregistrement
final pointera sur la valeur NIL.
Pour commencer, voici un type structuré simple qui pourrait convenir. En fait la valeur pourrait être n’importe quoi, et
le type prendra juste un entier quelconque.
TYPES
// Un élément de liste chaînée
Structure element
valeur:entier
pSuiv←NIL:pointeur sur element
FinStruct
Cette déclaration initiale du type structuré element contient un pointeur pSuiv (pour Pointeur sur Suivant) sur une
structure du même type. Par défaut il est initialisé à la valeur NIL : il n’y a pas encore d’enregistrement suivant. Que
pouvezvous faire de cette structure ? Tout d’abord vous déplacer d’un élément à un autre de la liste. Pour ça, il suffit
de partir du premier élément, et de récupérer, en boucle, le pointeur de l’élément suivant, jusqu’à tomber sur NIL.
Quelles sont les opérations élémentaires possibles sur une liste ?
q Créer une liste : c’est créer le premier enregistrement, celui de tête, qui permettra d’accéder aux autres.
q Parcourir une liste : c’est balayer tous les éléments, un par un, jusqu’au dernier.
q Rechercher un élément dans la liste : soit indiquer s’il existe, soit retourner un pointeur vers sa position.
q Ajouter un élément n’importe où dans la liste : au début, au milieu, à la fin. Une fonction d’ajout pourrait
aussi reprendre la première opération de création de liste.
q Supprimer un élément n’importe où dans la liste.
q Supprimer la liste.
Toutes ces actions peuvent se faire au travers de sousprogrammes, rendant l’usage de la liste beaucoup plus
simple. Pour se rapprocher des langages fonctionnels, les sousprogrammes devant le plus souvent retourner un
pointeur vers un élément de la liste.
Une dernière chose : le premier élément de la liste est toujours le point d’entrée pour la plupart des fonctions. Étant
donné qu’il sera représenté par la suite par un pointeur, ne perdez JAMAIS l’adresse de ce premier élément : il serait
impossible de retrouver le début de la liste, d’autant plus qu’avec l’allocation dynamique de mémoire, il est plus que
possible que les zones mémoires allouées à chaque élément ne soient pas contiguës.
Conservez toujours l’adresse du premier enregistrement dans un pointeur prévu à cet effet dont vous ne
modifierez pas la valeur tout au long du programme, sauf si vous supprimez le premier élément ou toute la
liste.
b. Création
- 2 -
© ENI Editions - All rigths reserved - Jonifar lina
175
Pour accéder à un élément donné de la liste vous partez toujours du premier élément. De là connaissant l’adresse du
suivant par le pointeur psuiv, vous passez successivement aux n suivants. Quand le pointeur ne pointe sur plus rien
(null), c’est que l’enregistrement est le dernier.
Une liste chaînée de ce type est dite unilatère : l’accès aux éléments composant la liste est séquentiel (vous devez
lire les n éléments précédents pour accéder à celui voulu), et unidirectionnel.
Chaque élément de la liste est un enregistrement. Cet enregistrement peut contenir autant de champs que vous le
souhaitez, mais l’un d’eux sera un pointeur sur un enregistrement de même type. Quand vous rajouterez un
deuxième élément, vous placerez son adresse dans le pointeur du premier, et ainsi de suite. Chaque enregistrement
final pointera sur la valeur NIL.
Pour commencer, voici un type structuré simple qui pourrait convenir. En fait la valeur pourrait être n’importe quoi, et
le type prendra juste un entier quelconque.
TYPES
// Un élément de liste chaînée
Structure element
valeur:entier
pSuiv←NIL:pointeur sur element
FinStruct
Cette déclaration initiale du type structuré element contient un pointeur pSuiv (pour Pointeur sur Suivant) sur une
structure du même type. Par défaut il est initialisé à la valeur NIL : il n’y a pas encore d’enregistrement suivant. Que
pouvezvous faire de cette structure ? Tout d’abord vous déplacer d’un élément à un autre de la liste. Pour ça, il suffit
de partir du premier élément, et de récupérer, en boucle, le pointeur de l’élément suivant, jusqu’à tomber sur NIL.
Quelles sont les opérations élémentaires possibles sur une liste ?
q Créer une liste : c’est créer le premier enregistrement, celui de tête, qui permettra d’accéder aux autres.
q Parcourir une liste : c’est balayer tous les éléments, un par un, jusqu’au dernier.
q Rechercher un élément dans la liste : soit indiquer s’il existe, soit retourner un pointeur vers sa position.
q Ajouter un élément n’importe où dans la liste : au début, au milieu, à la fin. Une fonction d’ajout pourrait
aussi reprendre la première opération de création de liste.
q Supprimer un élément n’importe où dans la liste.
q Supprimer la liste.
Toutes ces actions peuvent se faire au travers de sousprogrammes, rendant l’usage de la liste beaucoup plus
simple. Pour se rapprocher des langages fonctionnels, les sousprogrammes devant le plus souvent retourner un
pointeur vers un élément de la liste.
Une dernière chose : le premier élément de la liste est toujours le point d’entrée pour la plupart des fonctions. Étant
donné qu’il sera représenté par la suite par un pointeur, ne perdez JAMAIS l’adresse de ce premier élément : il serait
impossible de retrouver le début de la liste, d’autant plus qu’avec l’allocation dynamique de mémoire, il est plus que
possible que les zones mémoires allouées à chaque élément ne soient pas contiguës.
Conservez toujours l’adresse du premier enregistrement dans un pointeur prévu à cet effet dont vous ne
modifierez pas la valeur tout au long du programme, sauf si vous supprimez le premier élément ou toute la
liste.
b. Création
- 2 -
© ENI Editions - All rigths reserved - Jonifar lina
175