Les listes chaînées en C++
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. Dans une liste chaînée, chaque objet de la collection est lié uniquement à l'objet suivant de la collection.
L'objet d'une liste chaînée s'appelle un nœud et se compose de deux parties : données et un pointeur. La partie données définit la valeur de l'objet ; la partie pointeur indique le nœud suivant. Dans une liste chaînée simple, nous pouvons passer au nœud suivant à partir de n'importe quel nœud, mais nous ne pouvons pas revenir au nœud précédent. Il existe une autre implémentation, appelée liste doublement chaînée.
Conception
Pour concevoir un conteneur comme une liste chaînée simple, nous utilisons deux types d'objets différents : la liste et le nœud.
Objets de type liste et nœud
Création d'objets
L'objet liste est créé dans la mémoire de pile parce que nous n'en utilisons qu'une seule instance ; les nœuds sont créés dans la mémoire de tas parce que le nombre de nœuds change lorsque nous insérons ou effaçons des nœuds. La figure ci-dessous illustre l'idée générale d'une liste chaînée simple.
Dans la conception illustrée dans la figure ci-dessus, l'objet de liste a un pointeur, entete, qui pointe vers le premier nœud et un type de données entier, cpt, qui contient le nombre de nœuds dans la liste chaînée. Pour accéder aux données et aux membres suivants d'un nœud à partir de l'objet liste, nous définissons un nœud comme une structure au lieu d'une classe car nous pouvons accéder directement à ses membres de données à partir de la classe liste ; les membres d'une structure sont publics par défaut.
Implémentation
Nous montrons comment nous implémentons notre collection linéaire d'objets en utilisant une liste chaînée simple. Pour mieux comprendre l'implémentation, nous développons d'abord le code en trois fichiers, puis nous expliquons les opérations graphiquement.
Définition d’objets Liste et Noeud
Le nœud ne possède que deux membres de données publiques : donnees (Template) et un pointeur vers le nœud suivant.
// Définition du noeud en tant que struct
template <typename T>
struct Noeud
{
T donnees;
Noeud <T>* suivant;
// Pour définir une liste doublement chaînée
// Noeud <T>* precedent;
};
La classe Liste possède deux données membres privées, entete et compteur, et une fonction membre privée, CreerNoeud, qui est utilisée pour créer un nouveau noeud à insérer dans la liste. Nous avons créé sept fonctions membres publiques, dont le constructeur, le destructeur, l'insertion d'un noeud dans une liste, la suppression d'un noeud d'une liste, l'obtention de la valeur des données d'un noeud à une position spécifique, l'affichage du contenu des données de tous les noeuds et le renvoi du nombre de noeuds dans la liste.
// Définition de la classe Liste
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;
};
Notre liste n'est pas une liste triée car il n'est pas courant d'avoir une liste triée utilisant une liste chaînée simple ; d'autres structures, telles qu'un arbre de recherche binaire, sont utilisées à cette fin. Bien que la structure de la liste dans la STL utilise des opérations spécifiques, telles que l'insertion, la suppression et la récupération de données dans les éléments au début et à la fin de la liste, nous utilisons uniquement les opérations de base décrites ci-dessus à ce stade.
Créer un nouveau nœud
C'est la méthode la plus simple, ici nous créons un objet temporaire temp, puis mettons à jour l'attribut de données à la valeur transmise à la fonction et initions le pointeur suivant à NULL (ou 0).
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
Nous avons utilisé un constructeur par défaut en stockant 0 dans le membre count et un pointeur nul (0) dans le membre entete.
// Constructeur
template <typename T>
Liste <T> :: Liste ():entete (NULL), compteur (0) {}
Destructeur
Le destructeur supprime tous les nœuds un par un et libère la mémoire du tas. La figure ci-dessous présente le cas d'une liste chaînée à deux nœuds.
// Destructeur
template <typename T>
Liste <T> :: ~Liste ()
{
Noeud <T>* del = entete;
while (entete){
entete = entete -> suivant;
delete del;
del = entete;
}
}
Taille de la liste chaînée
On retourne juste la valeur de compteur
template <typename T>
int Liste <T> :: taille () const{
return compteur;
}
Insérer un noeud
L'insertion se fait à un endroit spécifié. On peut avoir trois cas : insertion au début, insertion au milieu, ou insertion à la fin.
L'insertion au début peut être effectuée à l'aide de deux opérations (après avoir créé un nœud), comme le montre la figure ci-dessous.
L'insertion au milieu est plus complexe, comme le montre la figure ci-dessous. Il faut avoir un pointeur courant et le déplacer jusqu'au nœud situé avant la position d'insertion. Nous pouvons alors insérer le nœud.
L'insertion à la fin est un cas particulier d'insertion au milieu dans lequel le pointeur actuel doit se déplacer vers le dernier nœud. Le nouveau nœud est inséré après 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);
//Insertion au début
if (pos == 0){
nouveau -> suivant = entete;
entete = nouveau;
}
// Insertion au milieu
else{
Noeud <T>* courant = entete;
for (int i = 1; i < pos; i++){
courant = courant -> suivant;
}
nouveau -> suivant = courant -> suivant;
courant -> suivant = nouveau;
}
compteur++;
}
Supprimer un noeud
La suppression est appliquée à un nœud spécifique. Si la liste n'est pas vide, nous avons trois cas : suppression du premier nœud, suppression d'un nœud au milieu, ou suppression du dernier nœud.
La suppression du premier nœud est très simple et peut être effectuée comme le montre la figure ci-dessous.
La suppression d'un nœud au milieu est plus complexe. Nous devons avoir un pointeur courant pour pointer sur le nœud avant celui à supprimer. Nous pouvons alors utiliser un autre pointeur, del, pour pointer sur le nœud à supprimer. On peut alors effacer le nœud. La figure ci-dessous montre les opérations impliquées dans la suppression d'un nœud au milieu.
La suppression à la fin implique un processus similaire de suppression au milieu, mais nous devons déplacer le pointeur courant vers le nœud avant le dernier nœud.
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--;
}
Afficher la liste chaînée
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 noeud
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;
}
}
Le fichier d'en-tête liste.h et le programme principal
#ifndef LISTE_H
#define LISTE_H
#include <iostream>
#include <cassert>
using namespace std;
// Définition du noeud en tant que struct
template <typename T>
struct Noeud
{
T donnees;
Noeud <T>* suivant;
};
// Définition de la classe Liste
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"
// Constructeur
template <typename T>
Liste <T> :: Liste ():entete (NULL), compteur (0) {}
// Destructeur
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);
//Insertion au début
if (pos == 0){
nouveau -> suivant = entete;
entete = nouveau;
}
// Insertion au milieu
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 ( ){
// Instanciation d'une liste chainée liste
Liste <string> liste;
// Insertion de six noeuds dans la 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");
// Afficher les valeurs de noeuds
cout << "Afficher la liste" << endl;
liste.afficher ();
cout<<'\n';
// afficher les valeurs de trois noeuds
cout << "Afficher les donnees de quelques noeuds" << endl;
cout << liste.getNoeud (1) << endl;
cout << liste.getNoeud (3) << endl;
cout << liste.getNoeud (4) << endl;
cout<<'\n';
// Supprimer trois noeuds
cout << "Supprimer quelques noeuds et afficher la liste" << endl ;
liste.supprimer (0);
liste.supprimer (3);
liste.afficher ();
cout<<'\n';
// Afficher la liste apres la suppression
cout << "Nombre de noeuds dans la liste: " << liste.taille() ;
return 0;
}
Résultat
Afficher la liste Mostafa Omar Sara Mohamed Moneim Dounia Abdelmalek Afficher les donnees de quelques noeuds Omar Mohamed Moneim Supprimer quelques noeuds et afficher la liste Omar Sara Mohamed Dounia Abdelmalek Nombre de noeuds dans la liste: 5
