Liste chaînée simple
Une liste chaînée est une structure de données linéaire dans laquelle les éléments ne sont pas stockés dans des emplacements mémoire contigus. Chaque objet est lié uniquement à l'objet suivant par un pointeur.
Nœud L'unité de base d'une liste chaînée s'appelle un nœud. Il se compose de deux parties :
- données — la valeur stockée dans le nœud.
- suivant — un pointeur vers le nœud suivant de la liste.
precedent pour naviguer dans les deux sens.Conception
Objets Liste et Nœud
Pour concevoir une liste chaînée simple, on utilise deux types d'objets distincts : l'objet liste et l'objet nœud.
Création des objets en mémoire
L'objet liste est créé dans la mémoire de pile (une seule instance). Les nœuds sont créés dans la mémoire de tas car leur nombre varie dynamiquement à chaque insertion ou suppression.
L'objet liste contient un pointeur entete vers le premier nœud et un entier compteur indiquant le nombre de nœuds. Le nœud est défini comme une struct (membres publics par défaut) pour permettre un accès direct depuis la classe liste.
Implémentation
Définition du nœud et de la classe Liste
Le nœud est un struct template avec deux membres publics : donnees et suivant.
template <typename T>
struct Noeud {
T donnees;
Noeud<T>* suivant;
// Pour une liste doublement chaînée, ajouter :
// Noeud<T>* precedent;
};La classe Liste possède deux membres privés (entete et compteur), une méthode privée CreerNoeud, et sept méthodes publiques.
template <typename T>
class Liste {
private:
Noeud<T>* entete;
int compteur;
Noeud<T>* CreerNoeud(const T& valeur);
public:
Liste();
~Liste();
void inserer(int pos, const T& valeur);
void supprimer(int pos);
T& getNoeud(int pos) const;
void afficher() const;
int taille() const;
};Créer un nouveau nœud
template <typename T>
Noeud<T>* Liste<T>::CreerNoeud(const T& valeur) {
Noeud<T>* temp = new Noeud<T>;
temp->donnees = valeur;
temp->suivant = NULL;
return temp;
}Constructeur
template <typename T>
Liste<T>::Liste() : entete(NULL), compteur(0) {}Destructeur
Le destructeur parcourt la liste et libère chaque nœud un par un depuis la mémoire de tas.
template <typename T>
Liste<T>::~Liste() {
Noeud<T>* del = entete;
while (entete) {
entete = entete->suivant;
delete del;
del = entete;
}
}Taille de la liste
template <typename T>
int Liste<T>::taille() const {
return compteur;
}Insérer un nœud
L'insertion peut se faire à trois positions :
Insertion au début
Deux opérations suffisent après la création du nœud.
Insertion au milieu
On avance un pointeur courant jusqu'au nœud précédant la position d'insertion, puis on relie le nouveau nœud.
Insertion à la fin
Cas particulier de l'insertion au milieu : courant atteint le dernier nœud.
template <typename T>
void Liste<T>::inserer(int pos, const T& valeur) {
if (pos < 0 || pos > compteur) {
cout << "Erreur! La position est invalide." << endl;
return;
}
Noeud<T>* nouveau = CreerNoeud(valeur);
if (pos == 0) { // Insertion en tête
nouveau->suivant = entete;
entete = nouveau;
} else { // Insertion au milieu / fin
Noeud<T>* courant = entete;
for (int i = 1; i < pos; i++) {
courant = courant->suivant;
}
nouveau->suivant = courant->suivant;
courant->suivant = nouveau;
}
compteur++;
}Supprimer un nœud
Suppression du premier nœud
Suppression au milieu ou en fin
Un pointeur courant se positionne sur le nœud précédant celui à supprimer, puis un pointeur del cible le nœud à supprimer avant de libérer sa mémoire.
template <typename T>
void Liste<T>::supprimer(int pos) {
if (pos < 0 || pos > compteur - 1) {
cout << "Erreur! La position est invalide." << endl;
return;
}
if (pos == 0) { // Suppression en tête
Noeud<T>* del = entete;
entete = entete->suivant;
delete del;
} else { // Suppression au milieu / fin
Noeud<T>* courant = entete;
for (int i = 0; i < pos - 1; i++) {
courant = courant->suivant;
}
Noeud<T>* del = courant->suivant;
courant->suivant = courant->suivant->suivant;
delete del;
}
compteur--;
}Afficher la liste
template <typename T>
void Liste<T>::afficher() const {
if (compteur == 0) {
cout << "La liste est vide!" << endl;
return;
}
Noeud<T>* courant = entete;
while (courant != 0) {
cout << courant->donnees << endl;
courant = courant->suivant;
}
}Retourner la valeur d'un nœud
template <typename T>
T& Liste<T>::getNoeud(int pos) const {
if (pos < 0 || pos > compteur - 1) {
cout << "Erreur! La position est invalide";
assert(false);
} else if (pos == 0) {
return entete->donnees;
} else {
Noeud<T>* courant = entete;
for (int i = 0; i < pos; i++) {
courant = courant->suivant;
}
return courant->donnees;
}
}Fichiers complets et programme principal
#ifndef LISTE_H
#define LISTE_H
#include <iostream>
#include <cassert>
using namespace std;
template <typename T>
struct Noeud {
T donnees;
Noeud<T>* suivant;
};
template <typename T>
class Liste {
private:
Noeud<T>* entete;
int compteur;
Noeud<T>* CreerNoeud(const T& valeur);
public:
Liste();
~Liste();
void inserer(int pos, const T& valeur);
void supprimer(int pos);
T& getNoeud(int pos) const;
void afficher() const;
int taille() const;
};
#endif#ifndef LISTE_CPP
#define LISTE_CPP
#include "liste.h"
template <typename T>
Liste<T>::Liste() : entete(NULL), compteur(0) {}
template <typename T>
Liste<T>::~Liste() {
Noeud<T>* del = entete;
while (entete) {
entete = entete->suivant;
delete del;
del = entete;
}
}
template <typename T>
Noeud<T>* Liste<T>::CreerNoeud(const T& valeur) {
Noeud<T>* temp = new Noeud<T>;
temp->donnees = valeur;
temp->suivant = NULL;
return temp;
}
template <typename T>
void Liste<T>::inserer(int pos, const T& valeur) {
if (pos < 0 || pos > compteur) {
cout << "Erreur! La position est invalide." << endl;
return;
}
Noeud<T>* nouveau = CreerNoeud(valeur);
if (pos == 0) {
nouveau->suivant = entete;
entete = nouveau;
} else {
Noeud<T>* courant = entete;
for (int i = 1; i < pos; i++) courant = courant->suivant;
nouveau->suivant = courant->suivant;
courant->suivant = nouveau;
}
compteur++;
}
template <typename T>
void Liste<T>::supprimer(int pos) {
if (pos < 0 || pos > compteur - 1) {
cout << "Erreur! La position est invalide." << endl;
return;
}
if (pos == 0) {
Noeud<T>* del = entete;
entete = entete->suivant;
delete del;
} else {
Noeud<T>* courant = entete;
for (int i = 0; i < pos - 1; i++) courant = courant->suivant;
Noeud<T>* del = courant->suivant;
courant->suivant = courant->suivant->suivant;
delete del;
}
compteur--;
}
template <typename T>
T& Liste<T>::getNoeud(int pos) const {
if (pos < 0 || pos > compteur - 1) {
cout << "Erreur! La position est invalide";
assert(false);
} else if (pos == 0) {
return entete->donnees;
} else {
Noeud<T>* courant = entete;
for (int i = 0; i < pos; i++) courant = courant->suivant;
return courant->donnees;
}
}
template <typename T>
void Liste<T>::afficher() const {
if (compteur == 0) { cout << "La liste est vide!" << endl; return; }
Noeud<T>* courant = entete;
while (courant != 0) {
cout << courant->donnees << endl;
courant = courant->suivant;
}
}
template <typename T>
int Liste<T>::taille() const { return compteur; }
#endif#include "liste.cpp"
#include <string>
int main() {
Liste<string> liste;
liste.inserer(0, "Mostafa");
liste.inserer(1, "Omar");
liste.inserer(2, "Sara");
liste.inserer(3, "Mohamed");
liste.inserer(4, "Moneim");
liste.inserer(5, "Dounia");
liste.inserer(6, "Abdelmalek");
cout << "Afficher la liste" << endl;
liste.afficher();
cout << '\n';
cout << "Afficher les données de quelques nœuds" << endl;
cout << liste.getNoeud(1) << endl;
cout << liste.getNoeud(3) << endl;
cout << liste.getNoeud(4) << endl;
cout << '\n';
cout << "Supprimer quelques nœuds et afficher la liste" << endl;
liste.supprimer(0);
liste.supprimer(3);
liste.afficher();
cout << '\n';
cout << "Nombre de nœuds dans la liste : " << liste.taille();
return 0;
}Sortie
Afficher la liste Mostafa Omar Sara Mohamed Moneim Dounia Abdelmalek Afficher les données de quelques nœuds Omar Mohamed Moneim Supprimer quelques nœuds et afficher la liste Omar Sara Mohamed Dounia Abdelmalek Nombre de nœuds dans la liste : 5
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.