Les listes chaînées

Écrit le 03/07/2003 par DukeNukem
Dernière mise à jour : 02/02/2006

Introduction

Vous êtes en train de programmer votre jeu, et il vous faut à présent gérer les monstres présents dans votre univers. Comment procéder à cela ? Une solution simple est de créer un tableau contenant vos monstres :

CMonster monstres[ 100 ];  // les monstres

Ou bien de créer un tableau dynamique, pour pouvoir gérer le nombre de monstre en fonction du niveau. Ensuite, on y accéderait tout simplement avec un index :

// rendu de tous les monstres à l'écran
for( int i = 0; i < 100; i++ )
    monstres[i].Draw();

Maintenant imaginez que vous avez aussi des armes et des munitions. On pourrait encore une fois procéder de la même manière :

CWeapon armes[ 50 ];       // les armes
CAmmo munitions[ 200 ];    // les munitions

// ...

for( i = 0; i < 50; i++ )
    armes[i].Draw();

for( i = 0; i < 200; i++ )
    munitions[i].Draw();

Ça commence à devenir un petit peu fastidieux, car vous aurez sûrement encore d'autres types d'entités dans votre niveau à gérer !

À présent se pose un problème : il vous faut gérer les entités « roquette ». La spécialité de celles-ci c'est qu'elles sont créées au moment de tirer avec le lance-roquette, et qu'elles sont détruites (dans la mémoire) au moment de leur explosion. De plus, le nombre est inconnu. Il peut y en avoir 0, 2 comme 50 ou 100 selon votre type de jeu, selon votre niveau, etc. Ainsi il se pourrait bien que les roquettes 1, 2, 4 et 5 soient toujours dans le niveau, mais que la 3 viennent à être supprimée. Il y aurait donc un « trou » dans votre tableau. Vous pourriez alors le réutiliser pour une autre roquette, plus tard, mais avec tous ces inconvénients cités au-dessus, vous remarquez bien que pour gérer vos entités, les tableaux, c'est vraiment pas ce qu'il faut utiliser.

Alors comment faire ? Et bien la solution : les listes chaînées.

Les listes chaînées simples

Une liste chaînée (linked list) est composée de n½uds (node), chacun ayant un pointeur vers le n½ud suivant de la liste. Chaque n½ud « contient » ou « est » une entité. Pour clarifier un peu ceci, voici un schéma :

http://www.game-lab.com/images/tuts/linked_lists/01_simple_linkedlist.gif

Ainsi, le n½ud A pointe sur le n½ud B, le n½ud B pointe sur le n½ud C, etc., jusqu'au dernier n½ud, le E, qui pointe sur NULL. L'avantage ici, c'est que l'on peut faire exécuter la même fonction pour chaque n½ud de la liste en n'appelant cette fonction que pour le premier n½ud. Voici un exemple simple d'implémentation :

class CNode
{
    // ...

public:
    void DrawList( void );

private:
    void DrawThisNode( void );

private:
    // pointeur sur le noeud suivant
    CNode *m_pNextNode;
};


void CNode::DrawList( void )
{
    // dessine ce noeud
    DrawThisNode();

    // dessine le noeud suivant s'il existe
    if( m_pNextNode != NULL )
        m_pNextNode->DrawList();
}


void CNode::DrawThisNode( void )
{
    // dessine l'objet de ce noeud
}

Et pour dessiner toute la liste d'objets, il suffit d'appeler la fonction DrawList() du premier n½ud :

// dessine toute la liste
NodeA->DrawList()

Cependant, ce modèle n'est toujours pas approprié à notre exemple de départ. Rappelez-vous les roquettes, ces entités que l'on créait au tir et que l'on détruisait à l'impact. Ici la création ne poserait pas de problèmes, la nouvelle roquette serait placée en queue de liste (où en tête, tout dépend de votre implémentation de la liste chaînée), mais à la destruction, si d'autres objets se sont glissés entre le bout de la liste et cette roquette et qu'on l'on supprimerait cette dernière de la liste, ces autres objets seraient perdus ! On aurait plus aucun moyen de les récupérer :

http://www.game-lab.com/images/tuts/linked_lists/02_simple_linkedlist.gif

On a toujours accès au premier noeud (A) mais pas aux autre. Le segment D-E est donc perdu.

Conséquence grave : les objets perdus, créés dynamiquement, seraient perdus dans la mémoire à jamais. Il faudrait alors pouvoir dire au n½ud précédent, de pointer maintenant sur le n½ud suivant. Le problème : nous n'avons pas de pointeur sur le n½ud précédent. Et bien nous allons en mettre un ! Nous allons créer une liste doublement chaînée !

Les listes doublement chaînées

Une liste doublement chaînée est une liste chaînée simple mais avec en plus un pointeur sur le n½ud précédent :

http://www.game-lab.com/images/tuts/linked_lists/03_double_linkedlist.gif

Maintenant que nous avons un pointeur à la fois sur l'élément suivant et sur l'élément précédent, on peut retirer un n½ud de la liste en refaisant les liens des n½uds suivant et précédents pour qu'ils se connectent ensemble :

http://www.game-lab.com/images/tuts/linked_lists/04_double_linkedlist.gif

Voyons maintenant un exemple d'implémentation de liste chaînée :

// ==============================================
// CNode - noeud d'une liste chaînée.
// ==============================================

class CNode
{
public:
    // constructeur/destructeur
    CNode( void )    { m_pNextNode = m_pPrevNode = 0; m_bIsManager = false; }
    virtual ~CNode( void );


public:
    // fonctions publiques
    bool    IsLastNode( void )  { return (m_pNextNode ? false : true); }
    bool    IsFirstNode( void ) { return !IsLastNode(); }
    bool    IsAlone( void )     { return ((m_pPrevNode && m_pNextNode) ? false : true); }
    bool    IsManager( void )   { return m_bIsManager; }

    void    SetManager( bool manager ) { m_bIsManager = manager; }
    void    Attach( CNode *node );
    void    UnLink( void );


protected:
    // variables membres
    CNode   *m_pNextNode;
    CNode   *m_pPrevNode;

    bool    m_bIsManager;
};

La classe est assez simple. On y retrouve donc deux pointeurs vers des objets CNode : le n½ud suivant (m_pNextNode) et le n½ud précédent (m_pPrevNode). On y trouve également une variable booléenne : m_bIsManager. Cette variable nous servira à affecter à un n½ud la tache de « manager », c'est à dire celui par lequel on fera exécuter les fonctions à tous les autres n½uds de la liste, et qui détruira automatiquement ces n½uds à sa propre destruction.

Ces variables membres sont protégées car nos objets qui vont être liés entre eux vont hériter de la classe CNode, et ils auront besoin d'avoir accès à ces variables.

Dans le constructeur, on initialise les deux pointeurs sur NULL (0). Ainsi à sa création le n½ud est seul, il n'appartient à aucune liste. Le destructeur est virtuel, pour la même raison que les variables protégées.

Ensuite, on trouve quatre fonctions pour savoir si le n½ud est le premier de la liste, s'il est aussi le dernier, s'il est seul ou s'il est le manager de la liste.

La fonction SetManager() permet de spécifier un n½ud comme manager ou pas.

La fonction Attach() a pour objectif de lier un n½ud à la liste. Elle doit être appelée par un n½ud de la liste (le manager par exemple) et prend en paramètre le n½ud à lier.

La fonction UnLink() quant à elle permet de délier un n½ud d'une liste, et de renouer les liens entre les n½uds précédent et suivant.

Passons maintenant au code de ces deux dernières fonctions et du destructeur :

// ----------------------------------------------
// destructeur - détruit les autres nodes de la
// liste si celui-ci en est le manager.
// ----------------------------------------------

CNode::~CNode( void )
{
    if( m_bIsManager )
    {
        if( !IsLastNode() )
        {
            m_pNextNode->SetManager( true );
            delete m_pNextNode;
            m_pNextNode = 0;
        }
    }

    UnLink();
}

À la destruction, si le n½ud est manager il doit s'assurer de la destruction de tous les n½uds de sa liste. Pour cela, il va faire passer le n½ud suivant en manager et le détruire, celui-ci étant manager va à son tour faire manager son n½ud suivant puis va le détruire, et ainsi de suite jusqu'au dernier.

Une fois ceci fait (s'il est manager), il se délie et renoue les liens des n½uds précédents et suivant avec la fonction UnLink().

// ----------------------------------------------
// UnLink() - détache ce noeud de la liste.
// ----------------------------------------------

void CNode::UnLink( void )
{
    if( m_pPrevNode )
        m_pPrevNode->m_pNextNode = m_pNextNode;

    if( m_pNextNode )
        m_pNextNode->m_pPrevNode = m_pPrevNode;

    m_pPrevNode = 0;
    m_pNextNode = 0;
}

Voici justement UnLink(). Si le n½ud n'est pas le premier de la liste, on fait pointer le n½ud suivant du n½ud précédent sur le n½ud suivant du n½ud à détacher. Si le n½ud n'est pas le dernier de la liste, on fait pointer le n½ud précédent du n½ud suivant sur le n½ud précédent du n½ud à détacher. C'est pas très simple avec les mots, référez vous au schéma précédent ;)

Enfin les deux pointeurs vont maintenant pointer sur NULL. Ce n½ud pourra éventuellement rejoindre une autre liste.

// ----------------------------------------------
// Attach() - attache "node" à la fin de la liste
// de celui-ci.
// ----------------------------------------------

void CNode::Attach( CNode *node )
{
    // on vérifie si le noeud n'est pas déjà dans la
    // liste chaînée...

    if( node->IsAlone() )
    {
        if( IsLastNode() )
        {
            m_pNextNode = node;

            node->m_pPrevNode = this;
            node->m_pNextNode = 0;
        }
        else
        {
            m_pNextNode->Attach( node );
        }
    }
}

Cette fonction attache le n½ud « node » (en paramètre) à la liste dont le n½ud ayant appelé cette fonction appartient.

Tout d'abord, on vérifie que le lien est bien seul et qu'il n'appartient pas déjà à une autre liste chaînée. Ensuite, si ce le n½ud « attachant » (celui qui a appelé cette fonction) est le dernier de la liste, on relie node. Sinon, on demande au n½ud suivant d'attacher node à la liste. Si lui non plus n'est pas le dernier, il demande au suivant, etc. Au final, node se retrouve à la fin de la liste chaînée. On aurait pus aussi le lier directement après le n½ud « attachant », c'est à vous d'essayer, de voir ce qui vous convient le mieux...

Tout ceci doit paraître bien théorique, je vous propose donc un exemple d'utilisation.

Exemple d'utilisation d'une liste doublement chaînée

Nous allons créer une liste qui contiendra toutes les entités de notre programme. Il y aura à la fois des monstres et des véhicules ! Pour ceci, on va d'abord créer une classe générique pour les entités : CEntity. Toutes les entités seront des classes dérivées de celle-ci, elle-même dérivée de CNode :

#include    <iostream>
#include    <string>

// ==============================================
// CEntity - entité quelconque.
// ==============================================

class CEntity : public CNode
{
public:
    // constructeur/destructeur
    CEntity( void ) { m_name = ""; }
    CEntity( std::string name ) { m_name = name; }

    virtual ~CEntity() { std::cout << "destroying " << m_name << std::endl; }


public:
    // fonctions publiques
    void DrawEntity( void )
    {
        // dessine cette entité
        Draw();

        // dessine l'entité suivante
        if( !IsLastNode() )
            ((CEntity *)m_pNextNode)->DrawEntity();
    };


private:
    // fonctions privées
    virtual void Draw( void ) { }


protected:
    std::string     m_name;
};

Pour faire simple, la seule fonction que l'on fera exécuter pour toute notre liste sera la fonction Draw() (par le biais de DrawEntity()) chargée d'afficher ici le type d'entité dessinée et son nom (stocké dans la variable membre m_name). Pour cette opération, on fera appeler DrawEntity() par l'entité manager qui fera dessiner l'entité, puis demandera à la suivante de se dessiner et de dessiner les suivantes de la liste.

Voyons maintenant les entités « monstre » et « véhicule » :

// ==============================================
// CMonster - entité monstre.
// ==============================================

class CMonster : public CEntity
{
public:
    // constructeur
    CMonster( std::string name ) { m_name = name; }

private:
    // fonctions privées
    virtual void    Draw( void ) { std::cout << "Drawing monster " << m_name << std::endl; }
};



// ==============================================
// CVehicle - entité véhicule.
// ==============================================

class CVehicle : public CEntity
{
public:
    // constructeur
    CVehicle( std::string name ) { m_name = name; }

private:
    // fonctions privées
    virtual void    Draw( void ) { std::cout << "Drawing vehicle " << m_name << std::endl; }
};

Ces deux classes sont très similaires, à l'exception que l'une écris à l'écran « Drawing monster » et l'autre « Drawing vehicle » (ce qui nous permettra de les distinguer dans notre exemple).

Bien, nous pouvons maintenant passer à la fonction main() :

// ----------------------------------------------
// main() - fonction principale.
// ----------------------------------------------

int main( int argc, char *argv[] )
{
    // création du premier node
    std::cout << "# creating linked list :" << std::endl;
    CEntity     *pEntityManager = new CEntity( "entity manager" );

    // création des autres nodes
    CMonster    *headcrab   = new CMonster( "headcrab" );
    CMonster    *bullsquid  = new CMonster( "bullsquid" );
    CVehicle    *car        = new CVehicle( "car" );
    CVehicle    *airplane   = new CVehicle( "airplane" );

    // on attache les nodes au premier de la liste
    pEntityManager->SetManager( true );
    pEntityManager->Attach( headcrab );
    pEntityManager->Attach( bullsquid );
    pEntityManager->Attach( car );
    pEntityManager->Attach( airplane );
    pEntityManager->Attach( new CMonster( "zombie" ) );

    // on dessine la liste des nodes
    pEntityManager->DrawEntity();

    // on retire un node de la liste
    std::cout << std::endl << "# removing car :" << std::endl;
    car->UnLink();

    // on redessine la liste puis on rattache le node car à la liste
    pEntityManager->DrawEntity();
    pEntityManager->Attach( car );

    // en détruisant le node manager, on détruit automatiquement les autres
    std::cout << std::endl << "# destroying linked list :" << std::endl;
    delete pEntityManager;

    return 0;
}

Dans un premier temps, on crée le manager (pEntityManager). Ensuite, on crée quatre classes dérivées de CEntity : deux monstres et deux véhicules. On attribue le statut de manager à pEntityManager, et on attache à la liste les quatre entités que l'on vient de créer.

On dessine chaque entité en n'appelant qu'une fois la fonction, via le manager. On retire un élément de la liste (car), on redessine. Vous voyez que la chaîne n'a pas été brisée.

On rattache car à la liste pour que l'objet soit automatiquement détruit avec les autres éléments de la liste lors de la destruction du manager.

À l'exécution, vous devriez avoir quelque chose comme ceci :

http://www.game-lab.com/images/tuts/linked_lists/05_final_linkedlist.gif

Utiliser la STL

Outre la possibilité de créer votre propre classe pour créer des listes chaînées, vous pouvez également utiliser la STL. Cette puissante bibliothèque comporte différentes classes et permet de nombreuses possibilités, évidemment, lorsque l'on connais leur possibilités ;)

L'avantage de l'utilisation de la STL est qu'elle fait partie du standard C++ (donc chaque compilateur C++ doit obligatoirement être capable de compiler un programme utilisant la STL) et que son code qui a été testé maintes fois est sûre (celui de CNode ½ qui n'était qu'un exemple d'implémentation des listes doublement chaînées ½ ne doit pas être infaillible). De plus, elle est 100% portable. Il n'y a donc aucune raison de s'en priver.

Je vais montrer ici le même exemple que précédemment mais cette fois en utilisant la classe std::list<> au lieu de notre classe CNode. Nous allons devoir légèrement modifier notre classe CEntity :

#include    <iostream>
#include    <string>
#include    <list>

// ==============================================
// CEntity - entité quelconque.
// ==============================================

class CEntity
{
public:
    // constructeur/destructeur
    CEntity( void ) { m_name = ""; }
    CEntity( std::string name ) { m_name = name; }

    virtual ~CEntity() { std::cout << "destroying " << m_name << std::endl; }


public:
    // fonctions privées
    virtual void Draw( void ) { }


protected:
    std::string     m_name;
};

CEntity n'hérite plus de CNode, la fonction DrawEntity() ne nous est plus utile, on va donc directement appeler Draw(). Cette dernière passe donc en mode public.

// ----------------------------------------------
// main() - fonction principale.
// ----------------------------------------------

int main( int argc, char *argv[] )
{
    // création du premier node
    std::cout << "# creating linked list :" << std::endl;
    std::list<CEntity *>            EntityList;
    std::list<CEntity *>::iterator  itor;

    // création des entités
    CMonster    *headcrab   = new CMonster( "headcrab" );
    CMonster    *bullsquid  = new CMonster( "bullsquid" );
    CVehicle    *car        = new CVehicle( "car" );
    CVehicle    *airplane   = new CVehicle( "airplane" );

    // on place les entités dans la liste
    EntityList.push_back( headcrab );
    EntityList.push_back( bullsquid );
    EntityList.push_back( car );
    EntityList.push_back( airplane );
    EntityList.push_back( new CMonster( "zombie" ) );

    // on dessine la liste d'entités
    for( itor = EntityList.begin(); itor != EntityList.end(); itor++ )
        (*itor)->Draw();


    // on retire "car" de la liste
    std::cout << std::endl << "# removing car :" << std::endl;

    itor = EntityList.begin();
    std::advance( itor, EntityList.size() - 3 );
    EntityList.erase( itor );

    // on redessine la liste puis on rattache "car" à la liste
    for( itor = EntityList.begin(); itor != EntityList.end(); itor++ )
        (*itor)->Draw();

    EntityList.push_back( car );


    // destruction des objets de la liste
    std::cout << std::endl << "# destroying linked list :" << std::endl;

    for( itor = EntityList.begin(); itor != EntityList.end(); itor++ )
        delete (*itor);

    return 0;
}

Je ne vais pas expliquer ici en détail le fonctionnement des classes de la STL, si vous êtes intéressés, voyez un article ou un livre spécialisé sur la STL.

Pour parcourir la liste, on utilise un itérateur. Cet itérateur est un objet CEntity** (donc un pointeur sur CEntity*). On dessine la liste en faisant se déplacer ce pointeur du premier objet (EntityList.begin()) jusqu'au dernier (EntityList.end()) en appelant la fonction (Draw()) à chaque fois.

On utilise la fonction std::advance() pour déplacer l'itérateur à la position voulue. Le premier paramètre est l'itérateur à déplacer, le second est le nombre d'objets à parcourir en partant de la position actuelle. On appelle EntityList.erase() pour retirer l'entité de la liste, sans la supprimer !

On redessine, on rajoute « car » à la liste, puis on détruit chaque élément en reparcourant la liste et en détruisant l'objet pointé par l'itérateur.

Conclusion

Cet article avait pour but de vous initier aux listes chaînées, qui peuvent être utilisée pour de nombreuses applications diverses, et beaucoup plus efficaces qu'un tableau dans certains cas. La classe CNode présentée ici est un exemple simple d'implémentation d'une liste chaînée, qui est loin d'être parfaite :) Il existe une infinité de possibilités, selon vos besoins et selon vos goûts, c'est à vous de voir. Ou si vous préférez utiliser la STL (même si elle fait peur aux débutants, je vous encourage tout de même à profiter des possibilités et des simplicités qu'elle peut apporter).

Le code source des exemples de ce tutorial est disponible ici.

Creative Commons Logo Contrat Creative Commons

Cet article est mis à disposition sous un contrat Creative Commons (licence CC-BY-ND).

http://tfc.duke.free.fr/coding/linked_list.html -->