3 - Les Listes Lineaires Chaines

ALGORITHME AVANCE
Chapitre 3:
Les listes linéaires chaînées
Semestre III
Licence 2 Info
Sommaire
1. Introduction
2. Rappel sur les pointeurs
3. Gestion dynamique de la mémoire
4. Définition d’une liste chaînée
5. Opération sur une liste chaînée
6. Les listes chaînées particulières
7. Conclusion
15/04/2023 2
1. Introduction
Dans la première partie de ce module (Initiation à l’algorithmique), nous avons vu et manipulé les types simples de données
(entier, réel, caractère, booléen), le type Tableau et le type Chaîne de caractères. Ce sont les types prédéfinis d’un langage de
programmation (ils existent tels quels).
Tous les langages de programmation offrent à l’utilisateur la possibilité de définir de nouveaux types de données plus
sophistiqués, permettant d’imaginer des traitements à la fois plus performants et plus souples. C’est ce que nous étudierons
dans ce chapitre.
Nous avons déjà vu comment le tableau permettait de désigner sous un seul nom un ensemble de valeurs de même type,
chacune d’entre elles étant repérée par un indice.
L’enregistrement, quant à elle, nous a permis de désigner sous un seul nom un ensemble de valeurs pouvant être de types
différents. L’accès à chaque élément de la structure (nommé Champ ou membre) s’effectue, cette fois, non plus par une
indication de position, mais par son nom au sein de la structure.
15/04/2023 3
2.Rappel sur les pointeurs
Lorsqu’on déclare une variable et ce, quel que soit le langage de programmation, le compilateur réserve en mémoire
l’espace nécessaire au contenu de cette variable à une donnée. Toute variable possède donc une adresse en mémoire. La
plupart du temps on ne s’intéresse pas à ces adresses. Mais quelque fois, ce type de renseignement peut s’avérer fort utile.
Un pointeur est une variable qui au lieu de contenir l’information (donnée, valeur) proprement dite, contient l’adresse
mémoire d’une autre entité informatique.
A la différence de la variable X classique qui contient
directement l’information « 71 », la variable Y déclarer
comme pointeur contient son adresse. On dit que Y pointe
vers l’information « 71 » grâce à son contenu, qui est
l’adresse de cette information.
15/04/2023 4
2.Rappel sur les pointeurs
Syntaxe de déclaration d’une variable pointeur :
<NomVariable> : ↑ <Type de donnée pointée>
Exemple : age : ↑ Entier taille : ↑ Réel
Note : Pour affecter une valeur à une variable pointeur, on utilise le symbole & (Et commercial) qui est appelé
opérateur d’adressage.
Illustration : a : Entier // a variable de type entier

taille : ↑ Entier // taille variable pointeur sur un entier
a  17 // affectation d’une valeur à la variable a
taille  &a // affectation d’une valeur à la variable pointeur taille
15/04/2023 5
3. Gestion dynamique de la mémoire
Deux procédures permettent de gérer dynamiquement la mémoire :
- La procédure nouveau (p : pointeur) qui permet à chaque appel d’obtenir (allouer ou réserver)
un espace mémoire dont l’adresse sera retournée dans la variable pointeur p.
- La procédure liberer (p : pointeur) qui permet de libérer (laisser ou abandonner) un espace
mémoire d’adresse p dont on a plus besoin.
Ces deux procédures permettent d’obtenir et de rendre un espace mémoire au fur et à mesure des besoins
de l’algorithme. On parle de gestion dynamique de la mémoire contrairement à la gestion statique des
tableaux (taille ou dimension fixe).
15/04/2023 6
Une liste chaînée est un ensemble d’élément d’information appelés nœuds (ou maillon). En plus de l’information dont
il est porteur, un nœud possède un champ pointeur.
Ce pointeur contient l’adresse du nœud suivant dans la liste.
Une liste chaînée est déterminée grâce à l’adresse de son premier nœud. Cette adresse doit être sauvegarder dans une
variable pointeur que nous appellerons très souvent début ou tête.
 Représentation graphique d’un nœud :

Pointeur vers nœud
Information
suivant
Nœud
 Représentation graphique d’une liste chaînée simple :
Tete Adresse1
Info1 Adresse2 Info2 Adresse3 Info3 AdresseN InfoN NULL
Nœud_1 Nœud_2 Nœud_3 Nœud_N

15/04/2023 7
Une liste chainée n’est pas limitée à un nombre fixe d’élément. On peut insérer et supprimer des éléments de la liste
autant que nécessaire, et ce, sans avoir besoin de connaitre, à priori, le nombre d’élément de la liste : c’est la gestion
dynamique de la mémoire. Elle apporte donc une réponse optimale à bon nombre de problèmes d’implantation de
l’information dans un algorithmes
 Syntaxe de déclaration d’un nœud : On définit un type nommé pointeur sur une variables de type nœud, puis
TYPE pointeur = ↑ nœud on définit le type nœud. Une variables P de type pointeur contient l’adresse
nœud = structure
d’une variable de type nœud. La variable P peut être représentée
membre_1 : Type1
membre_2 : Type2 schématiquement par :
...... Adresse1
membre_n : TypeN
suivant : pointeur
Fin_structure membre_1 membre_2 … membre_n Suivant
Information
L’adresse du nœud est rangée dans la variable P. par abus de langage, on dira : nœud d’adresse P ou nœud
pointé par P. Le nœud contient deux parties : La partie information contenant les variables membre1,
membre2, … et le pointeur suivant contenant une adresse.
15/04/2023 8
On accède aux variables membres du nœud d’adresse P grâce à l’opérateur point ( . ) comme suit :
P↑. membre1, P↑.membre2, …
On accède de la même façon à l’adresse contenue dans le nœud d’adresse P :
P↑.suivant
15/04/2023 9
5. Opération sur les listes chaînées
Dans ce qui suit, nous allons créer, consulter, insérer et supprimer des éléments d’un liste chaînée. Pour
ce faire, considérons que chaque nœud « Personne » de la liste contient deux informations : un
entier « numéro » et une chaîne de caractère « nom » de 20 caractères.
TYPE pointeur = ↑ Personne

Personne = structure
Numero : entier
Nom : chaîne de 20 caractères
Suivant : pointeur
Fin_structure
15/04/2023 10
5.1. Création d’une liste chaînée simple
Principe :
Procédure CreerListe(Tete : ^Liste, Elt : entier) : Vide
1. Déclarer et Initialiser la Tete à vide (Nil) ;
Variables :
2. Allouer un espace mémoire P pour le
P : ^Liste
premier nœud grâce à la procédure
Début
allouer ou nouveau; TeteNil
3. Stocke la valeur dans le champ Allouer(P)
Information du nœud pointé par P ; P^.ValeurElt
4. P suivant est Nil, s’il n'y a pas d'élément P^.Suivant Nil
suivant ; TeteP
5. Le pointeur Tete pointe maintenant sur P. Fin
FinProcedure
Supposons que nous voulions créer la liste chaînée qui soit la représentation des nœuds de type « Personne ». On
déclare pour cela deux pointeurs « tete » et « courant » de type « Personne » :
- « tete » pour contenir l’adresse du 1er élément de la liste ;
- « courant » pour contenir l’adresse de l’élément en cours (celui qui subit un traitement).
15/04/2023 11
5. Opération sur les listes chaînées Début
Nouveau(Tete)
5.1. Création d’une liste chaînée simple courant  Tete
Algorithme Création_Liste Répéter
TYPE pointeur = ↑ Personne Ecrire (Entrez le numéro de la personne )
Personne = structure Lire (courant↑.Numero)
Numero : entier Ecrire ( Entrez le nom de la personne )
Nom : chaîne de 20 caractères Lire (courant↑.Nom)
suivant : pointeur Ecrire( Autre élément o/n ? )
Fin_structure Lire(Reponse)
Variables : Si (Reponse == o) alors
Tete, courant : pointeur Nouveau(courant↑.suivant)
Reponse : Car Courant  courant↑.suivant
Sinon
Le contenu de la variable pointeur « tete » est fixe : elle contient
Courant ↑.suivant  nil
la même valeur tout le long du programme, l’adresse du 1er
Fsi
nœud de la liste.
Jusqu’à (Reponse == n)
Le contenu de la variable pointeur « courant » change tout au
Fin
long du programme : elle contient l’adresse du nœud en cours de
FinAlgorithme
traitement.
15/04/2023 12
5.2. Consultation (affichage) d’une liste chaînée simple
Pour consulter la liste chaînée que nous avons crée

Algorithme Consultation_Liste
précédemment, il faut se repositionner au début (tête)
de la liste, puis la parcourir nœud par nœud jusqu’à la Variables :
fin. Tete, courant : pointeur
Début
Courant  Tete
Tant que (courant<>Nil) faire
Ecrire (courant↑.numero)
Ecrire (courant↑.nom)
Courant  courant↑.suivant
Fin tant que
Fin
FinAlgorithme
15/04/2023 13
5.3. Insertion d’un élément dans une liste chaînée
Dans une liste chaînée, on peut insérer autant d’éléments qu’on souhaite avec seulement la modification d’un ou deux
pointeurs sans recopie ni décalage des éléments non par la mise à jour. L’insertion d’un élément peut se faire en tête,
en queue ou dans une position k de la liste.
5.3.1. Insertion d’un élément en tête de liste chaînée

Insérer un nouvel élément en tête de la liste se fait en trois étapes :
a) On réserve un nouvel espace mémoire et on récupère son adresse dans un pointeur de type « Personne » appelé,
par exemple « NouvElmt » ;
b) On saisit les informations véhiculées par le nouveau nœud ;
c) On effectue le chaînage du nouveau nœud avec la liste existante. Ce nœud devient le 1er élément de la nouvelle
liste.
15/04/2023 14
Simulation sur une liste d’entier :
On souhaite insérer un nouvel élément en tête de liste.
Déchainage
Tete @4
@1
Chainage
premier
12 @2 27 @3 16 Nil
élément
Chainage
33 @1
Réservation d’un espace mémoire
15/04/2023 15
Algorithme Insertion_En_Tete_De_Liste
Variables :
Tete, NouvElmt : pointeur
Début
Nouveau (NouvElmt)
Lire (NouvElmt ↑.numero)
Lire (NouvElmt ↑.nom)
NouvElmt↑.suivant  Tete
Tete  NouvElmt
Fin
FinAlgorithme
15/04/2023 16
5.3.1. Insertion d’un élément en queue de liste chaînée
Insérer un nouvel élément en queue de la liste se fait en quatre étapes :
a) On réserve un nouvel espace mémoire et on récupère son adresse dans un pointeur de type « Personne » appelé, par
exemple « NouvElmt » ;
c) On se positionne sur le dernier élément de la liste. Pour ce faire on la parcourt du début à la fin. Le dernier élément de
la liste est celui pour lequel le « suivant » est égal à « Nil »
d) On effectue le chaînage du nouveau nœud avec la liste existante. Ce nœud devient le dernier élément de la nouvelle
liste.
15/04/2023 17
On souhaite insérer un nouvel élément à la queue de liste.
Courant
@2
@1
@3
Parcours de la liste
Chainage
31 Nil
@1
Tete
5 @2 28 @3 Val-3
9 Nil
@4
Dernier de la liste
Déchainage
15/04/2023 18
Algorithme Insertion_En_Queue_De_Liste
Variables :
Tete, Courant, NouvElmt : pointeur
Début
Nouveau (NouvElmt)
Lire (NouvElmt ↑.numero)
Lire (NouvElmt ↑.nom)
Courant  Tete
Tant que (Courant↑.suivant <>Nil) faire
Courant  Courant↑.suivant
Fin tantque
Courant↑.suivant  NouvElmt
NouvElmt↑.suivant  Nil
Fin
15/04/2023 FinAlgorithme 19
5.3.1. Insertion d’un élément à une position k dans liste chaînée
Insérer un nouvel élément en queue de la liste se fait en quatre étapes :
a) On réserve un nouvel espace mémoire et on récupère son adresse dans un pointeur de type « Personne » appelé, par
exemple « NouvElmt » ;
c) On effectue la recherche du nœud après lequel insérer le nouvel élément.
d) On effectue le chaînage du nouveau nœud avec la liste existante. Ce nœud prend sa place après celui recherché.
15/04/2023 20
5.3.1. Insertion d’un élément à une position k dans liste chaînée
On souhaite insérer un nouvel élément à la position : 3

position
Courant @1
@2
Recherche de la position
@1
Tete
21 @2 54 @3
@4 117 Nil
Déchainage
Chainage
Chainage
86 @3
15/04/2023 21
Algorithme Insertion_Position_k_Dans_Liste
5.3. Insertion d’un élément dans une: liste chaînée
Variables
5.3.1. Insertion d’un élément à une positionTete,

k Courant,
dans liste chaînée
NouvElmt : pointeur
Num : entier

Début
Nouveau (NouvElmt)
Lire (NouvElmt↑.numero)
Lire (nom)
Ecrire ("Entrer le numéro de la personne après lequel insérer")
Lire (Num)
Courant  Tete
Tant que (Courant <>Nil) faire
Si (Num == Courant↑.numero ) alors
NouvElmt↑.suivant  Courant↑.suivant
Courant↑.suivant  NouvElmt
Fsi
Fin tant que
Fin
FinAlgorithme
15/04/2023 22
5.3. Suppression d’un élément dans une liste chaînée
Dans une liste chaînée, on peut supprimer un ou plusieurs éléments avec mise à jour d’un ou deux pointeurs et
restitution des espaces mémoires occupés par ces éléments. La suppression d’un élément peut s’effectuer en tête, en
queue ou à une position k donnée.
5.3.1. Suppression d’un élément en tête de liste chaînée
Supprimer le premier élément de la liste se fait en deux étapes :

a) On libère l’espace mémoire occupé par le premier nœud de la liste en utilisant la procédure « Liberer ».
b) On met à jour l’adresse de la nouvelle tête de la liste.
15/04/2023 23
On souhaite supprimer un élément à la tête de la liste.
Tete
Chainage nouvelle tête
@1
@2
Courant
Déchainage
@1 Val-1 @3 Val-2 @4 Val-3 Nil
Pointage
sur le nœud Val-1 @2 Déchainage
à supp
Nœud à supprimer
15/04/2023 24
Algorithme Suppression_En_Tete_De_Liste
Variables :
Tete, Courant : pointeur
Début
Courant  Tete
Tete  Tete↑.suivant
Liberer (Courant)
Fin
FinAlgorithme
15/04/2023 25
5.3.1. Suppression d’un élément en queue de liste chaînée
La suppression du dernier élément d’une liste se fait en trois étapes :

a) On se positionne sur l’avant dernier élément de la liste. Pour ce faire on la parcourt à partir du début, élément par
élément jusqu’à trouver l’avant dernier. L’avant dernier élément d’une liste est celui dont le pointeur « suivant »
du « suivant » est égal à « Nil ».
b) On libère l’espace mémoire occupé par le dernier élément de la liste (qui se trouve être le suivant de l’élément
courant).
c) On fait en sorte que l’avant dernier élément de la liste devienne le dernier.
15/04/2023 26
On souhaite supprimer un élément en queue de la liste.
Recherche de l’avant dernier élément
Courant @3
@1
@2
Nœud à supprimer
Déchainage
Tete @1
Val-2 @3 Val-3 Nil
@4 Val-4 Nil
Chainage nouvelle
queue
Val-1 @2
15/04/2023 27
Algorithme Suppression_En_Queue_De_Liste
Variables :
Tete, Courant : pointeur
Début
Courant Tete
Tant que (Courant↑.suivant↑.suivant <>Nil) faire
Fin tantque
Liberer (Courant↑.suivant)
Courant↑.suivant  Nil
Fin
FinAlgorithme
15/04/2023 28
5.3.1. Suppression d’un élément à une position k dans liste chaînée
La suppression d’un élément dans une position donnée dans une liste se fait en trois étapes :
a) On effectue la recherche du nœud à supprimer. On peut faire la recherche avec le numéro de la personne en
commençant par le 2nd élément de la liste.
b) On libère l’espace occuper par l’élément à supprimer.
c) On met à jour le pointeur « suivant » de l’élément précédent celui à supprimer.
15/04/2023 29
5.3.1. Suppression d’un élément à une position k dans liste chaînée

On souhaite supprimer un élément à une position donnée dans la liste.
Valeur du nœud à
supprimer Recherche du nœud à supprimer
@2
@3
Nil
15
Courant
Déchainage Déchainage
Num
31 @4
@3 15 @4 73 Nil
Nœud à supprimer
Actulisation
10 @2 du précédent
@1 Chainage
Pointage dur @2
@1
Tete le 1er noeud
Precedent
15/04/2023 30
Algorithme Suppression_ Position_k_Dans_Liste
5.3. Suppression d’un élément dans une liste chaînée Variables :
5.3.1. Suppression d’un élément à une position k dans liste chaînée Tete, Courant, Precedent : pointeur
Num :entier
Début
Ecrire ("Entrer le numéro de la personne a supprimer")
Lire (Num)
Precedent Tete
Courant Tete↑.suivant
Tant que (Courant <>Nil) faire
Si (Num = = Courant↑.numero) alors
Precedent↑.suivant  Courant↑.suivant
Liberer (Courant)
Courant  nil // pour quitter la boucle

Sinon
Precedent  Courant
Fsi
Fin tantque
Fin
6.1. Listes chaînées bidirectionnelles (listes doublement chaînées)
Les listes chaînées que nous avons précédemment peuvent être qualifier de simples ou monodirectionnelles car on ne
peut les parcourir que dans un seul sens : de gauche à droite.
Si on veut pouvoir effectuer un parcours de droite à gauche, il faut ajouter un pointeur permettant l’accès au nœud
précèdent. On qualifie alors la liste de bidirectionnelle. Compte tenu de la place supplémentaire occupée en mémoire.
On utilise cette possibilité que dans le cas où on a très souvent besoin d’effectuer un retour en arrière vers la tête de la
liste.
Pour faciliter le parcours de droite à gauche, on mémorise l’adresse du dernier nœud dans une variable pointeur que
nous appellerons très souvent « fin ».
15/04/2023 32
 Représentation graphique d’un nœud :
Pointeur vers Adresse Pointeur vers Adresse

Information
Précédent Suivant
Nœud
 Représentation graphique d’une liste chaînée bidirectionnelle :
Adr1 Tête Adr3 Fin
Nil Info1 Adr2 Adr1 Info2 Adr3 Adr2 Info3 Nil
Nœud_1 Nœud_3
Nœud_2
15/04/2023 33
 Syntaxe de déclaration d’un nœud :
TYPE pointeur = ↑ nœud

nœud = structure
membre_1 : Type1
membre_2 : Type2
......
membre_n : TypeN
Suivant, Precedent : pointeur
Fin_structure
15/04/2023 34
6.1.1. Création d’une listes chaînées bidirectionnelles
 Le principe reste assez similaire à celui d’une liste simple, sauf qu’il faut gérer le pointeur « precedent » de chaque
nœud créer.
 Le pointeur « precedent » du premier nœud ainsi que le pointeur « suivant » du dernier nœud contiennent la valeur
« Nil ».
15/04/2023 35
6.1.1. Création d’une listes chaînées bidirectionnelles

Début
Algorithme Création_Liste_Bidirectionnelle
Nouveau(Tete)
TYPE pointeur = ↑ Personne
courant↑.suivant  Nil
Personne = structure
courant  Tete
Numéro : entier
Répéter
Nom : chaîne de 20 caractères
Ecrire (Entrez le numéro et le nom de la personne)
suivant, precedent : pointeur
Lire (courant↑.numero, courant↑.nom)
Fin_structure
Ecrire(Autre élément o/n ?)
Variables :
Lire(Reponse)
Tete, courant, fin : pointeur
Si (Reponse == ‘o’) alors
Reponse : Car
Nouveau(courant↑.suivant)
courant↑.suivant↑.precedent  courant
courant  courant↑.suivant
Sinon
Courant ↑.suivant  nil
Fin  courant
FinSi
Jusqu’à Reponse = = ‘n’
Fin
Algorithme Consultation_Liste_Bidirectionnelle
6.1. Listes chaînées bidirectionnelles (listes doublementVariables :

chaînées)
tete, courant, fin : pointeur
6.1.2. Consultation d’une listes chaînées bidirectionnelles choix : entier
Début
Une fois la liste doublement chaînée créée, on Ecrire ("1-Consultation par la gauche 2-Consultation par la droite ")
Ecrire ("Entrez votre choix : ")

peut la parcourir de la tête à la fin (gauche- Lire (choix)
Si (choix == 1) alors
droite) ou de la fin à la tête (droite-gauche). Le
courant  tete
principe est le même que pour une liste chaînée Tant que (courant<>Nil) faire
Ecrire (courant↑.numero, " ", courant↑.nom)

simple.
Courant  courant↑.suivant
Fin tantque
SinonSi (choix == 2) alors
courant  fin
Tant que (courant<>Nil) faire
Ecrire (courant↑.numero, " ", courant↑.nom)
Courant  courant↑.precedent
Fin tant que
FinSi
Fin
FinAlgorithme
15/04/2023 37
6.1.3. Insertion d’un élément en tête d’une listes chaînées bidirectionnelles
L’insertion en tête de la liste d’un nouvel élément se fait Algorithme Insertion_En_Tete_De_Liste_Bidrectionnelle
comme suit : Variables :

tete, NouvElmt : pointeur
a) On réserve un nouvel espace mémoire à Début
l’adresse « NouvElmt » ; Nouveau (NouvElmt)
Lire (NouvElmt ↑.numero, NouvElmt ↑.nom)
b) On saisit les informations véhiculées par le nouveau
NouvElmt↑.precedent  Nil
nœud ;
tete↑.suivant  NouvElmt
c) On initialise le pointeur « precedent » du nouveau NouvElmt↑.suivant  tete
nœud à Nil. tete  NouvElmt
Fin
d) On effectue le chaînage du nouveau nœud avec la liste
FinAlgorithme
existante.
e) On met à jour l’adresse de la nouvelle tete de liste.
15/04/2023 38
6.1.3. Suppression d’un élément en tête d’une listes chaînées bidirectionnelles
La suppression du 1er élément de la liste se fait Algorithme Suppression_En_Queue_De_Liste_Bidirectionnelle

comme suit : Variables :
tete : pointeur
a) On libère l’espace mémoire occupé par
Début
le 1er nœud.
Liberer (tete)
b) On met à jour l’adresse de la nouvelle
Tete  tete↑. suivant
tête de la liste.
tete↑.precedent  Nil
c) La nouvelle tête de liste n’a pas de
Fin
précédent.
FinAlgorithme
15/04/2023 39
6.2. Listes chaînées circulaires
Une liste chaînée peut être circulaire, c'est à dire que le pointeur du dernier élément contient l'adresse du premier.
Dans une liste circulaire tous les maillons sont accessibles à partir de n’importe quel autre maillon. Une liste circulaire
n’a pas de premier et de dernier maillon. Par convention, on peut prendre le pointeur externe de la liste vers le dernier
élément et le suivant serait le premier élément de la liste.
Ci-dessous l'exemple d'une liste simplement chaînée circulaire : le dernier élément pointe sur le premier.
Adresse1 Tête
Info1 Adresse2 Info2 Adresse3 Info3 AdresseN InfoN Adresse1
Nœud_1 Nœud_2 Nœud_3 Nœud_N
15/04/2023 40
6.2. Listes chaînées circulaires
Puis l'exemple d'une liste doublement chaînée circulaire. : Le dernier élément pointe sur le premier, et le premier
élément pointe sur le dernier.
Adr1 Tête Fin Adr3
Adr3 Info1 Adr2 Adr1 Info2 Adr3 Adr2 Info3 Adr1
Nœud_1 Nœud_2 Nœud_3
15/04/2023 41
7. Conclusion
L'avantage des listes chaînées est donc de ne plus utiliser des tableaux de pointeurs (Tableau dynamique)
pour pointer les éléments instanciés. Chaque élément est simplement relié au suivant par un pointeur,
voire également au précédent si nécessaire par un second pointeur.
Car les tableaux de pointeurs déclarés grâce à l’opérateur new sont toujours de longueur fixe.
15/04/2023 42

3 - Les Listes Lineaires Chaines

Transféré par

Droits d'auteur :

Formats disponibles

3 - Les Listes Lineaires Chaines

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

3 - Les Listes Lineaires Chaines

Transféré par

Droits d'auteur :

Formats disponibles

ALGORITHME AVANCE

2. Rappel sur les pointeurs

3. Gestion dynamique de la mémoire

4. Définition d’une liste chaînée

5. Opération sur une liste chaînée

6. Les listes chaînées particulières

Illustration : a : Entier // a variable de type entier

Ce pointeur contient l’adresse du nœud suivant dans la liste.

 Représentation graphique d’un nœud :

Info1 Adresse2 Info2 Adresse3 Info3 AdresseN InfoN NULL

Nœud_1 Nœud_2 Nœud_3 Nœud_N

P↑. membre1, P↑.membre2, …

On accède de la même façon à l’adresse contenue dans le nœud d’adresse P :

TYPE pointeur = ↑ Personne

Pour consulter la liste chaînée que nous avons crée

5.3.1. Insertion d’un élément en tête de liste chaînée

On souhaite insérer un nouvel élément en tête de liste.

Réservation d’un espace mémoire

Insérer un nouvel élément en queue de la liste se fait en quatre étapes :

Insérer un nouvel élément en queue de la liste se fait en quatre étapes :

Simulation sur une liste d’entier :

On souhaite insérer un nouvel élément à la position : 3

Réservation d’un espace mémoire

5.3.1. Insertion d’un élément à une positionTete,

5.3.1. Suppression d’un élément en tête de liste chaînée

Supprimer le premier élément de la liste se fait en deux étapes :

On souhaite supprimer un élément à la tête de la liste.

La suppression du dernier élément d’une liste se fait en trois étapes :

Recherche de l’avant dernier élément

Simulation sur une liste d’entier :

Courant  nil // pour quitter la boucle

 Représentation graphique d’un nœud :

Pointeur vers Adresse Pointeur vers Adresse

Adr1 Tête Adr3 Fin

Nil Info1 Adr2 Adr1 Info2 Adr3 Adr2 Info3 Nil

 Syntaxe de déclaration d’un nœud :

TYPE pointeur = ↑ nœud

6.1.1. Création d’une listes chaînées bidirectionnelles

6.1.1. Création d’une listes chaînées bidirectionnelles

Courant ↑.suivant  nil

Jusqu’à Reponse = = ‘n’

6.1. Listes chaînées bidirectionnelles (listes doublementVariables :

6.1.2. Consultation d’une listes chaînées bidirectionnelles choix : entier

Ecrire ("Entrez votre choix : ")

Ecrire (courant↑.numero, " ", courant↑.nom)

SinonSi (choix == 2) alors

Tant que (courant<>Nil) faire

Ecrire (courant↑.numero, " ", courant↑.nom)

Fin tant que

6.1.3. Insertion d’un élément en tête d’une listes chaînées bidirectionnelles

L’insertion en tête de la liste d’un nouvel élément se fait Algorithme Insertion_En_Tete_De_Liste_Bidrectionnelle

comme suit : Variables :

6.1.3. Suppression d’un élément en tête d’une listes chaînées bidirectionnelles

La suppression du 1er élément de la liste se fait Algorithme Suppression_En_Queue_De_Liste_Bidirectionnelle

Info1 Adresse2 Info2 Adresse3 Info3 AdresseN InfoN Adresse1

Nœud_1 Nœud_2 Nœud_3 Nœud_N

Adr1 Tête Fin Adr3

Adr3 Info1 Adr2 Adr1 Info2 Adr3 Adr2 Info3 Adr1

Nœud_1 Nœud_2 Nœud_3