Chapitre 02

Listes Simplement Chaînées

Structures de Données — Explication Complète avec Visualisations

■ Ce que tu vas apprendre

1. Définition et intuition d'une liste chaînée

2. Anatomie d'une cellule (champs d, suivant)
3. Déclaration de la structure (mot par mot)
4. Opérations : Taille, Contient, Kième
5. Ajout : en début, en fin, en position k
6. Suppression : en début, en fin, en position k
 1 Intuition — C'est quoi une Liste Chaînée ?

Imagine des post-its sur ton bureau. Chaque post-it contient une information ET une flèche vers le post-it
suivant. Le dernier dit NIL = 'je suis le dernier'.

k=1 k=2 k=3

Liste
Ali Sara Nour NIL

■ Propriété clé : si tu connais l'adresse de la première cellule, tu peux accéder à toute la liste en suivant les
flèches.

Définition formelle
Une LSC (Liste Simplement Chaînée) est une structure dynamique : sa taille augmente ou diminue en
mémoire selon les besoins du programme. Chaque élément est une cellule avec deux compartiments.

Anatomie d'une cellule

Compartiment Nom Contient

Gauche d La vraie donnée (entier, nom, etc.)

Droite suivant L'adresse de la prochaine cellule (ou NIL)

 2 Déclaration de la Structure — Mot par Mot

Algorithme : Déclaration

Type cellule = Enregistrement

d : Type_donnee
suivant : ^cellule
Fin cellule

pointeur = ^cellule
Liste = ^cellule

MOT / SYMBOLE SIGNIFICATION

Type cellule On crée un nouveau type de variable qu'on appelle 'cellule'

= Enregistrement Structure qui regroupe plusieurs champs (comme une fiche)

d Nom du champ donnée — contient la valeur stockée

: Type_donnee Type de la donnée (entier, chaîne...) — générique, à remplacer

suivant Nom du champ lien — pointe vers la cellule suivante

^cellule ^ = pointeur VERS. Donc 'pointeur vers une cellule'

pointeur Alias pour ^cellule — une variable qui stocke une adresse

Liste Alias pour ^cellule — représente l'adresse de la 1ère cellule

■ Clé de compréhension : Liste n'est pas toute la liste — c'est juste l'adresse du premier élément. Si tu perds
cette adresse, tu perds tout !
 3 Opération : Taille — Compter les cellules

Algorithme : Taille(L)

Fonction Taille(val L : Liste) : entier

Debut
p <- L // curseur part du début
m <- 0 // compteur = 0
Tant que (p <> NIL) faire
m <- m + 1 // on compte cette cellule
p <- p^.suivant // on avance au suivant
Fin tant que
Retourner(m) // résultat final
Fin

MOT / SYMBOLE SIGNIFICATION

val L : Liste L = la liste passée en lecture seule (val = pas de modification)

: entier La fonction retourne un entier (le nombre de cellules)

p <- L p est notre 'curseur' — on le place sur la 1ère cellule

m <- 0 m = compteur, initialisé à 0

p <> NIL Tant que p pointe vers une vraie cellule (pas la fin)

m <- m + 1 On vient de voir une cellule, on incrémente le compteur

p^.suivant p^ = aller à l'adresse de p | .suivant = champ lien

Retourner(m) On retourne le compteur final = nombre total de cellules

Trace d'exécution — Liste [10 → 20 → 30]

k=1 k=2 k=3

Liste
10 20 30 NIL

Tour p pointe sur p ≠ NIL ? m Action

Départ cellule(10) ✓ 0 on entre dans la boucle

1 cellule(10) ✓ 1 m=1, p avance → cellule(20)

2 cellule(20) ✓ 2 m=2, p avance → cellule(30)

3 cellule(30) ✓ 3 m=3, p avance → NIL

4 NIL ✗ 3 on sort → Retourner(3) ✓

 4 Opération : Kième — Accéder à la cellule k

Cette fonction est fondamentale car elle est utilisée par les opérations d'ajout et de suppression en
position k. Elle retourne le pointeur vers la k-ième cellule.

Algorithme : Kième(L, k)

Fonction Kieme(val L : Liste ; val k : entier) : pointeur

Debut
p <- L
i <- 1 // compteur de position
Tant que (p <> NIL) faire
Si (i = k) alors
Retourner(p) // on est à la position k !
p <- p^.suivant // avancer
i <- i + 1 // incrémenter la position
Fin tant que
Retourner(NIL) // k dépasse la taille
Fin

MOT / SYMBOLE SIGNIFICATION

i <- 1 i = numéro de la position courante, on part de 1

Si (i = k) On vérifie si on est arrivé à la position demandée

Retourner(p) On retourne l'adresse de cette cellule

i <- i + 1 Sinon on continue et on incrémente la position

Retourner(NIL) Si on sort sans trouver k → k est invalide (trop grand)

Trace pour k=2 — Liste [10 → 20 → 30]

k=1 k=2 k=3

Liste
10 20 30 NIL

↑ La cellule en surbrillance (k=2) est celle retournée par Kième(L,2)

 5 Opération : Ajout

5.1 — Ajout en début de liste

On veut insérer une nouvelle valeur avant la première cellule. Il faut d'abord créer la cellule, puis la
connecter à l'ancienne tête.

Algorithme : Ajout_Début(L, x)

Procedure Ajout_Debut(Var L : Liste ; val x : Type_donnee)

Debut
nouveau(p) // crée une cellule, p = son adresse
p^.d <- x // met la valeur dans le champ d
p^.suivant <- L // p pointe vers l'ancienne 1ère cellule
L <- p // L pointe maintenant vers p
Fin

AVANT :
20 30 NIL

Ajout de 10 en début

APRÈS :
10 20 30 NIL

MOT / SYMBOLE SIGNIFICATION

nouveau(p) Réserve une case en mémoire, met son adresse dans p

p^.d <- x p^ = aller à l'adresse de p | .d = champ donnée | <- x = y mettre x

p^.suivant <- L Le nouveau 1er élément doit pointer vers l'ANCIEN 1er

L <- p L doit pointer vers le NOUVEAU 1er élément

5.2 — Ajout en position k

On veut insérer une valeur à la position k. On doit se placer sur la cellule k-1, créer la nouvelle cellule, et
la connecter entre k-1 et k.
Algorithme : Ajout en position k

Procedure Ajout(Var L : Liste ; val k : entier ; val x : Type_donnee)

Debut
Si (k = 1) alors
Ajout_Debut(L, x) // cas spécial
Sinon
p <- Kieme(L, k-1) // aller à la cellule k-1
Si (p = NIL) alors
Afficher('Position invalide')
Sinon
nouveau(C) // créer la nouvelle cellule
C^.d <- x // mettre la valeur
q <- p^.suivant // q = ancienne cellule k
p^.suivant <- C // k-1 pointe vers C
C^.suivant <- q // C pointe vers l'ancienne k
Fin

AVANT :
10 30 NIL

Ajout de 15 en position k=2

APRÈS :
10 15 30 NIL
 6 Opération : Suppression

6.1 — Suppression en début de liste

On supprime la première cellule. On sauvegarde son adresse dans p pour pouvoir la libérer, puis on
avance L.

Algorithme : Suppression_Début(L)

Procedure Suppression_Debut(Var L : Liste)

Debut
Si (L = NIL) alors
Afficher('Suppression impossible: liste vide')
Sinon
p <- L // sauvegarder l'adresse de la 1ère cellule
L <- L^.suivant // L avance vers la 2ème cellule
Liberer(p) // libérer la mémoire de l'ancienne 1ère
Fin

AVANT :
10 20 30 NIL

Suppression du début (10 supprimé)

APRÈS :
20 30 NIL

MOT / SYMBOLE SIGNIFICATION

L = NIL Vérification : si la liste est vide, impossible de supprimer

p <- L On sauvegarde l'adresse de la 1ère cellule dans p

L <- L^.suivant L pointe maintenant sur la 2ème cellule (nouveau début)

Liberer(p) On libère la mémoire occupée par l'ancienne 1ère cellule

6.2 — Suppression en fin de liste

 Algorithme : Suppression_Fin(L)

Procedure Suppression_Fin(Var L : Liste)

Debut
Si (L = NIL) alors
Afficher('Liste vide')
Sinon si (L^.suivant = NIL) alors // une seule cellule
Liberer(L)
L <- NIL
Sinon
p <- L
Tant que (p^.suivant^.suivant <> NIL) faire
p <- p^.suivant // avancer jusqu'à l'avant-dernier
Fin tant que
Liberer(p^.suivant) // libérer le dernier
p^.suivant <- NIL // l'avant-dernier devient le dernier
Fin

AVANT :
10 20 30 NIL

Suppression de la fin (30 supprimé)

APRÈS :
10 20 NIL

MOT / SYMBOLE SIGNIFICATION

p^.suivant^.suivant On regarde 2 cellules en avance pour s'arrêter à l'AVANT-dernier

p^.suivant = NIL Cas spécial : une seule cellule → on libère directement

Liberer(p^.suivant) Libère la dernière cellule

p^.suivant <- NIL L'avant-dernier devient le nouveau dernier (pointe vers NIL)
 7 Suppression en Position k

Algorithme : Suppression(L, k)

Procedure Suppression(Var L : Liste ; val k : entier)

Debut
Si (k = 1) alors
Suppression_Debut(L) // cas spécial
Sinon
p <- Kieme(L, k-1) // aller à la cellule k-1
Si (p = NIL) alors
Afficher('Position invalide')
Sinon
q <- p^.suivant // q = cellule à supprimer
Si (q = NIL) alors
Afficher('Position invalide')
Sinon
p^.suivant <- q^.suivant // 'sauter' q
Liberer(q) // libérer la mémoire
Fin

Schéma — Suppression en position k=2

k=1 k=2 k=3

Avant
10 20 30 NIL

p=k-1 q=k (à suppr.) k+1

k=1 k=2

Après
10 30 NIL

MOT / SYMBOLE SIGNIFICATION

p <- Kieme(L, k-1) On se place sur la cellule AVANT celle à supprimer

q <- p^.suivant q = cellule à supprimer (position k)

p^.suivant <- q^.suivant On 'enjambe' q : k-1 pointe directement vers k+1

Liberer(q) q est déconnecté → on libère sa mémoire

 8 Résumé de Toutes les Opérations

Opération But Complexité

Taille(L) Compter le nombre de cellules O(n)

Kième(L, k) Retourner la k-ième cellule O(k)

Contient(L, x) Chercher si x est dans la liste O(n)

Ajout_Début(L, x) Insérer x en 1ère position O(1)

Ajout(L, k, x) Insérer x à la position k O(k)

Suppression_Début(L) Supprimer le 1er élément O(1)

Suppression_Fin(L) Supprimer le dernier élément O(n)

Suppression(L, k) Supprimer l'élément en position k O(k)

■ Points Clés à Retenir

→ Une liste = pointeur vers la 1ère cellule (NIL si vide)

→ Chaque cellule = { d (donnée) | suivant (adresse suivante) }
→ p^.d = accéder au champ donnée de la cellule pointée par p
→ p^.suivant = accéder au champ lien de la cellule pointée par p
→ Toujours Liberer() une cellule supprimée pour éviter les fuites mémoire
→ Ajout/Suppression en début : O(1) | En fin ou position k : O(n)