C++ > Avancé > Les listes chaînées

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 :

Monster 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 :

Weapon armes[50];     // les armes
Ammo munitions[200];  // les munitions

// ...

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

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

Bon, vous sentez bien qu'à ce rythme là on est mal barré s'il faut rajouter les véhicules, les murs, les rochers, les machins, les caisses et tous ça. Vous aurez certainement encore bien 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 Node
{
  // ...

public:
  void drawList ();

private:
  void drawThisNode ();

private:
  // Pointeur sur le noeud suivant
  Node *_nextNode;
};

void
Node::drawList ()
{
  // Dessine ce noeud
  drawThisNode ();

  // Dessine le noeud suivant s'il existe
  if (_nextNode != NULL)
    _nextNode->drawList ();
}

void
Node::drawThisNode ()
{
  // 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 :

Destruction du nœud C
Le nœud B pointe sur NULL ; Plus personne ne pointe sur le nœud D

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 :

Destruction du nœud C
Les liaisons ont été rétablies

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

/////////////////////////////////////////////////////////////////////////////
//
// Node - noeud d'une liste doublement chaînée.
//
/////////////////////////////////////////////////////////////////////////////

class Node
{
public:
  // Constructeur/destructeur
  Node ()
    : _nextNode (NULL), _prevNode (NULL), _isManager (false) { }
  virtual ~Node ();

public:
  // Interface publique
  bool isLastNode () { return (_nextNode ? false : true); }
  bool isFirstNode () { return !isLastNode (); }
  bool isAlone () { return ((_prevNode && _nextNode) ? false : true); }
  bool isManager () { return _isManager; }

  void setManager (bool manager) { _isManager = manager; }
  void attach (Node *node);
  void unLink ();

protected:
  // Variables membres
  Node *_nextNode;
  Node *_prevNode;

  bool _isManager;
};

La classe est assez simple. On y retrouve donc deux pointeurs vers des objets Node : le nœud suivant (_nextNode) et le nœud précédent (_prevNode). On y trouve également une variable booléenne : _isManager. 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 Node, et ils auront besoin d'avoir accès à ces variables.

Dans le constructeur, on initialise les deux pointeurs sur NULL. 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 :

// --------------------------------------------------------------------------
// Node::~Node
//
// Destructeur - détruit les autres nodes de la liste si celui-ci en est
// le manager.
// --------------------------------------------------------------------------

Node::~Node ()
{
  if (_isManager)
    {
      if (!isLastNode ())
        {
          _nextNode->setManager (true);
          delete _nextNode;
          _nextNode = 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().

// --------------------------------------------------------------------------
// Node::unLink
//
// Détache ce noeud de la liste.
// --------------------------------------------------------------------------

void
Node::unLink ()
{
  if (_prevNode)
    _prevNode->_nextNode = _nextNode;

  if (_nextNode)
    _nextNode->_prevNode = _prevNode;

  _prevNode = NULL;
  _nextNode = NULL;
}

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.

// --------------------------------------------------------------------------
// Node::attach
//
// Attache @node à la fin de la liste de celui-ci.
// --------------------------------------------------------------------------

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

  if (node->isAlone ())
    {
      if (isLastNode ())
        {
          _nextNode = node;

          node->_prevNode = this;
          node->_nextNode = NULL;
        }
      else
        {
          _nextNode->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 : Entity. Toutes les entités seront des classes dérivées de celle-ci, elle-même dérivée de Node :

#include <iostream>
#include <string>

/////////////////////////////////////////////////////////////////////////////
//
// Entity - classe de base pour une entité.
//
/////////////////////////////////////////////////////////////////////////////

class Entity : public Node
{
public:
  // Constructeurs/destructeur
  Entity () { }
  Entity (std::string name)
    : _name (name) { }

  virtual ~Entity () { std::cout << "destroying " << _name << std::endl; }

public:
  // Interface publique
  void drawEntity ()
  {
    // Dessine cette entité
    draw ();

    // Dessine l'entité suivante
    if (!isLastNode ())
      dynamic_cast<Entity *>(_nextNode)->drawEntity ();
  }

private:
  // Fonctions internes
  virtual void draw () { }

protected:
    std::string _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 _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 » :

/////////////////////////////////////////////////////////////////////////////
//
// Monster - entité "monstre".
//
/////////////////////////////////////////////////////////////////////////////

class Monster : public Entity
{
public:
  // Constructeur
  Monster (std::string name)
    : Entity (name) { }

private:
  // Fonctions internes
  virtual void draw () { std::cout << "drawing monster " << _name << std::endl; }
};

/////////////////////////////////////////////////////////////////////////////
//
// Vehicle - entité "véhicule".
//
/////////////////////////////////////////////////////////////////////////////

class Vehicle : public Entity
{
public:
  // Constructeur
  Vehicle (std::string name)
    : Entity (name) { }

private:
  // Fonctions internes
  virtual void draw () { std::cout << "drawing vehicle " << _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() :

int
main ()
{
  // Création du premier node
  std::cout << "# creating linked list :" << std::endl;
  Entity *pEntityManager = new Entity ("entity manager");

  // Création des autres nodes
  Monster *headcrab = new Monster ("headcrab");
  Monster *bullsquid = new Monster ("bullsquid");
  Vehicle *car = new Vehicle ("car");
  Vehicle *airplane = new Vehicle ("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 Monster ("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 Entity : 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 Node — 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 Node. Nous allons devoir légèrement modifier notre classe Entity :

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

/////////////////////////////////////////////////////////////////////////////
//
// Entity - classe de base pour une entité.
//
/////////////////////////////////////////////////////////////////////////////

class Entity
{
public:
  // Constructeurs/destructeur
  Entity () { }
  Entity (std::string name)
    : _name (name) { }

  virtual ~Entity () { std::cout << "destroying " << _name << std::endl; }

public:
  // Interface publique
  virtual void draw () { }

protected:
  std::string _name;
};

Entity n'hérite plus de Node, la fonction drawEntity() ne nous est plus utile, on va donc directement appeler draw(). Cette dernière passe donc en mode publique.

int
main ()
{
  // Création du premier node
  std::cout << "# creating linked list :" << std::endl;
  std::list<Entity *> entityList;
  std::list<Entity *>::iterator itor;

  // Création des entités
  Monster *headcrab = new Monster ("headcrab");
  Monster *bullsquid = new Monster ("bullsquid");
  Vehicle *car = new Vehicle ("car");
  Vehicle *airplane = new Vehicle ("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 Monster ("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 Entity** (donc un pointeur sur Entity*). 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 Node 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 cet article sont réutilisables librement sans conditions particulières.