📌 Cours sur les Listes
Les listes sont des structures de données fondamentales utilisées pour stocker un
ensemble d'éléments. Il existe deux types principaux de listes :
1. Les listes contiguës (Tableaux dynamiques)
2. Les listes chaînées
1️ Les Listes Contiguës (Tableaux Dynamiques)
Une liste contiguë est une structure de données où les éléments sont stockés de
manière séquentielle en mémoire (comme un tableau).
📌 Caractéristiques :
Chaque élément est accessible directement par son indice.
La taille de la liste est généralement fixe (mais peut être agrandie si nécessaire).
Les opérations d'accès sont rapides (O(1)), mais l'ajout ou la suppression
d'éléments peut être coûteux (O(n)).
1 2 4 5 7 9
Lire(pos) ;
Pour i allant de pos a N-1 faire
T[i]T[i+1] ;
Pour i allant de N/2 a N+1 faire
T[i+1]T[1] ;
Fin
T[N/2]=x ;
📌 Opérations sur une Liste Contiguë :
1. Insertion d'un élément en fin (O(1)) ou au milieu (O(n))
2. Suppression d'un élément (O(n))
3. Accès à un élément par son indice (O(1))
4. Recherche d’un élément (O(n) en général)
2
️. Les Listes Chaînées
Une liste chaînée est une structure de données où chaque élément (appelé nœud)
contient :
Une valeur
3 @
Un lien vers le nœud suivant
📌 Caractéristiques : List L
Tet=@100
3 @130
5 @101
@100
@130
2 null
7 @140 @101
@140 Les éléments ne sont pas stockés de manière contiguë en mémoire.
La taille est dynamique (ajout et suppression faciles).
L'accès à un élément nécessite de parcourir la liste (O(n)).
📌 Types de Listes Chaînées :
1. Liste chaînée simple (chaque nœud pointe vers le suivant)
2. Liste doublement chaînée (chaque nœud a un lien vers le suivant et le précédent)
7 @140 suiv
3. Liste circulaire (le dernier nœud pointe vers le premier)
📌 Opérations sur une Liste Chaînée :
1. Insertion en début (O(1)) ou au milieu (O(n))
2. Suppression d'un élément (O(n))
3. Recherche d'un élément (O(n))
4. 📌 Comparaison des Deux Types de Listes
Liste Contiguë (Tableau
Caractéristiques Liste Chaînée
Dynamique)
Accès direct ✅ O(1) (indice) ❌ O(n) (parcours)
❌ O(n) (doit décaler les
Insertion/Suppression ✅ O(1) en tête
éléments)
📌 Espace fixe (allocation en
Mémoire 📌 Allocation dynamique
bloc)
🔹 Manipulation simple, accès 🔹 Structures évolutives et
Utilisation
rapide dynamiques
Noeud 4 null
@130
Temp=Tete
Tete =@130
X=3 3 @13 @13
X=4 0
Structure Noeud
Valeur: entier
Suivant: Noeud
P:Noeud
Fin Structure
Algorithme Liste_Chainee
Var
tete, Nouveau, Temp: Noeud;
x: entier;
Début
tete ← Null // Initialisation de la liste chaînée vide
// Ajout de plusieurs éléments en tête de liste
Répéter
Ecrire("Entrer une valeur (ou -1 pour arrêter) : ")
Lire(x)
Si x ≠ -1 Alors
Allouer(Nouveau)
[Link] ← x
Nouveau^.Suivant ← tete
tete ← Nouveau
Fin Si
Jusqu'à x = -1
// Affichage de la liste chaînée
Temp ← tete
Tant que Temp ≠ Null Faire
Afficher([Link])
Temp ← [Link]
Fin Tant que
Fin
Algorithme 1 : Suppression d’un élément recherché
Tet=@100 x=5 temp=Tet prec=temp [Link]==x
Tantque( [Link] !=x)&&([Link] !=null)
Prec =temp ;
Temp=[Link] ;
Prec=@100 Temp=@130
[Link]=[Link]
li
3 @130
5 @101
@100
@130
2 null
7 @140 @101
@140
Algorithme Supprimer_Element
Var
tete, Temp, Prec: Noeud;
x: entier;
Début
Ecrire("Entrer la valeur à supprimer : ")
Lire(x)
Temp ← tete
Prec ← Null
// Recherche de l'élément à supprimer
Tant que Temp ≠ Null et [Link] ≠ x Faire
Prec ← Temp
Temp ← [Link]
Fin Tant que
Si Temp = Null Alors
Ecrire("Élément non trouvé")
Sinon
// Si l'élément est en tête de liste
Si Prec = Null Alors
tete ← [Link]
Sinon
[Link] ← [Link]
Fin Si
Libérer(Temp) // Libérer la mémoire du nœud supprimé
Ecrire("Élément supprimé")
Fin Si
Fin
✅ Algorithme 2 : Recherche d’un élément dans la liste
Algorithme Rechercher_Element
Var
tete, Temp: Noeud;
x: entier;
Trouve: booléen
Début
Ecrire("Entrer la valeur à rechercher : ")
Lire(x)
Temp ← tete
Trouve ← Faux
Tant que Temp ≠ Null et Trouve = Faux Faire
Si [Link] = x Alors
Trouve ← Vrai
Sinon
Temp ← [Link]
Fin Si
Fin Tant que
Si(Temp=tete) Alors
Ecrire("pos1") ;
Si Trouve Alors
Ecrire("Élément trouvé")
Sinon
Ecrire("Élément non trouvé")
Fin Si
Fin
Exercice 1 :
Soit L une liste d’entiers. Écrire une procédure qui affiche l’élément du milieu de la liste
en utilisant un seul parcours.
n/2+1
Tet=@100 temp=tet=@100 p=tet=@100
Tet=@100 temp=tet=@100 p=tet=@100
Temp =[Link] ;p=[Link]
temp=@130 p=@100
temp=@101 p=@100
temp=@140 p=@130
temp=null p=@130
temp=tet p=tet
echange=0
tanque([Link] !=null)
temp=[Link] ;
si(echange mode 2 ==0 && echange !=0){
p=[Link]
echange=echange+1 ;
3 @130
5 @101
@100
@130
2 null
7 @140 @101
@140
Exercice 2 :
Soient deux listes chaînées d’entiers. Écrire les fonctions permettant de vérifier si elles
sont similaires ou comparables.
Deux listes sont similaires si elles contiennent les mêmes éléments, mais pas
forcément aux mêmes positions.
Exemple : {9,6,7,6,3,6,1,9} et {1,3,6,6,6,7,9,9} sont similaires.
Deux listes sont comparables si elles contiennent le même ensemble de valeurs,
sans prendre en compte la fréquence d’apparition des éléments.
Exemple : {1,3,6,7,9} et {9,6,7,6,3,6,1,9} sont comparables.
