Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies.


Politique de confidentialité
Introduction et syntaxe de base
Pointeurs et fonctions
Programmation OO
Structures de données
La bibliothèque standard (STL)

Les listes chaînées en C++

 

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

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.