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 :
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 :
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 :
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 :
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 :
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.
Cet article est mis à disposition sous un contrat Creative Commons (licence CC-BY-ND).
