C# – Énumérateur sur une liste simplement chaînée

Ceci est un exemple implémentant une liste simplement chaînée d'un type T quelconque en C#, cette liste exposant l'équivalent .NET d'un itérateur, version « ancienne » (itérant sur des object), utile pour utiliser foreach, et version contemporaine (itérant sur des T). Vous pourrez comparer par vous-mêmes avec des programmes équivalents dans les langages que vous connaissez.

Un exemple de programme entreposant ces chaînes de caractères dans une ListeSimple<string> est proposé à droite.

 
using System;
using System.Collections.Generic;

ListeSimple<string> lst = new ();
for (int i = 0; i < 10; ++i)
   lst.PushBack("mot #" + (i + 1));
foreach(string s in lst)
   Console.WriteLine(s);
while(!lst.Empty())
   Console.WriteLine(lst.PopBack());

Tout d'abord, le cas d'exception le plus probable dans l'implémentation d'une liste simplement chaînée est une tentative d'accès à un élément d'une liste vide. Pour cette raison, nous implémentons une classe représentant ce concept, et dérivant de la classe Exception de .NET.

 
class ListeVide : Exception { }

Une liste simplement chaînée d'éléments de type T (ici nommée ListeSimple<T>) entreposera des références sur des T. La généricité de .NET ne s'applique qu'à des classes (pas aux primitifs), ce qui signifie que T dérivera au moins indirectement de la classe object.

Dans le monde .NET, une collection de T sur laquelle il est possible d'itérer est dite énumérable, donc pouvant être énumérée. Ceci se fait de manière intrusive, en faisant dériver au préalable la collection en question de l'interface IEnumerable<T>.

Ce qui tient lieu d'itérateur sur des T dans le monde .NET est un énumérateur, donc une instance d'une classe dérivant de l'interface IEnumerator<T>.

Un énumérateur .NET nouvellement créé se trouve juste avant le premier élément de la séquence énumérable qu'il représente. Le code habituel de parcours d'une telle séquence sur un énumérateur e est :

while(e.MoveNext())
{
   // utiliser e.Current...
}

Clairement, il ne faut pas utiliser la propriété Current d'un énumérateur avant qu'une première invocation de MoveNext() n'ait été réalisée.

Les opérations essentielles d'un IEnumerator sont :

  • la méthode MoveNext(), qui mène au prochain élément de la séquence en cours d'énumération et retourne true seulement si cette opération a fonctionné;
  • la méthode Reset(), qui replace l'énumérateur en début (juste avant le premier élément) de séquence; et
  • la propriété Current, qui retourne une référence sur l'élément vers lequel mène l'énumérateur.

Pour des raisons historiques et techniques, un IEnumerator<T> est aussi un IEnumerator classique, itérant sur des références à des object, ce qui explique la version de Current au nom plus explicite et retournant un object (le long nom, pleinement qualifié, sert à lever une ambiguïté entre les deux versions de Current).

Remarquez le constructeur de notre classe d'énumérateurs, nommée Itérateur. La liste simplement chaînée étant structurée à l'aide de noeuds, chaque instance d'Itérateur se souvient à la fois du noeud initial (ici, un noeud « vide » menant vers le 1er noeud de la séquence) et du noeud courant.

Remarquez que Itérateur est une classe interne et privée. Le code client n'en verra que le parent, soit l'interface IEnumerator<T> (ou IEnumerator, selon les méthodes invoquées sur la liste simplement chaînée).

 
class ListeSimple<T> : IEnumerable<T>
{
   // Pour IEnumerable<T> (début)
   private class Itérateur
      : IEnumerator<T>
   {
      private Noeud cur,
                    init;
      public void Dispose()
      {
      }
      public bool MoveNext()
      {
         cur = cur.successeur;
         return cur != null;
      }
      public void Reset()
      {
         cur = init;
      }
      public T Current => cur.Valeur;
      object System.Collections.IEnumerator.Current =>
         cur.Valeur;
      public Itérateur(ListeSimple<T>.Noeud noeud)
      {
         cur = init = new Noeud(); // ugh!
         init.successeur = noeud;
      }
   }

Un IEnumerable<T> doit exposer une méthodeGetEnumerator() retournant un IEnumerator<T> capable de le parcourir.

Tout comme un IEnumerator<T> est aussi un IEnumerator classique itérant sur des références vers des object, un IEnumerable<T> est aussi un IEnumerable classique représentant une collection de références vers des object. Pour cette raison, une seconde version deGetEnumerator(), retournant un IEnumerable classique, doit être exposée par notre liste simplement chaînée.

 
   public IEnumerator<T> GetEnumerator() =>
      new Itérateur(tete);
   System.Collections.IEnumerator
      System.Collections.IEnumerable.GetEnumerator() =>
         new Itérateur(tete);
   // Pour IEnumerable<T> (fin)

Tout comme Itérateur, la classe Noeud est une classe interne et privée, représentant une unité d'entreposage pour un T.

Le constructeur par défaut ici est un constructeur bidon, qui ne sert qu'à créer des noeuds initiaux pour une séquence énumérable. Il est raisonnable d'y affecter default à valeur. 

   private class Noeud
   {
      public Noeud successeur = null; // ugh!
      private T valeur;
      public T Valeur => valeur;
      public Noeud()
      {
         valeur = default;
      }
      public Noeud(T val)
      {
         valeur = val;
      }
   }

Une liste nouvellement construite sera vide. La propriété Empty en fait foi : seule la tête est testée mais il est clair que si l'un des invariants de la liste simplement chaînée lst est que lst.Empty() <==> lst.tete==null, un autre sera que lst.tete==null<==>lst.queue==null.

Considérant les choix de représentation interne faits pour ListeSimple<T>, les algorithmes derrière les méthodes PushBack() et PushFront() seront tous deux de complexité . Les noms de ces méthodes sont d'inspiration C++; le monde .NET utiliserait sans doute Add(), InsertAtEnd() ou quelque chose de semblable.

 
// ...
   private Noeud tete,
                 queue;
   public ListeSimple()
   {
      tete = queue = null;
   }
   public bool Empty => tete == null;
   public void PushBack(T val)
   {
      if (Empty)
         tete = queue = new (val);
      else
      {
         queue.successeur = new (val);
         queue = queue.successeur;
      }
   }
   public void PushFront(T val)
   {
      if (Empty)
         tete = queue = new (val);
      else
      {
         Noeud p = new (val);
         p.successeur = tete;
         tete = p;
      }
   }

Un exemple de PopBack(), en apparence convenable mais illégal en pratique en C#, serait celui proposé à droite. Elle est coûteuse (complexité linéraire, donc ), mais notez que ce coût découle directement du choix de structure de données (une liste simplement chaînée) et est indépendant du langage de programmation choisi pour l'implémenter.

La raison de cette illégalité est le recours à deux variables de même nom (val). Même si ces variables sont placées dans deux portées distinctes de la méthode PopBack(), le compilateur juge incorrect le code proposé dans cet exemple. Ceci peut surprendre les informaticien(ne)s contemporain(e)s, peu habitué(e)s à de telles facéties, mais c'est la règle ici.

 
/*
   public T PopBack()
   {
      if (Empty)
         throw new ListeVide();
      if (tete == queue)
      {
         T val = tete.Valeur;
         tete = queue = null;
         return val;
      }
      Noeud p = tete;
      while (p.successeur != queue)
         p = p.successeur;
      T val = queue.Valeur;
      queue = p;
      p.successeur = null;
      return val;
   }
*/

Une implémentation légale en C# utilisera une seule variable val de type T, comme dans la version proposée à droite.

Notez que ce choix, bien qu'il pêche du point de vue de l'élégance, n'est pas très coûteux puisque val est une référence sur un T, pas un objet à proprement dit.

 
   public T PopBack() // coùteux (O(n))
   {
      if (Empty)
            throw new ListeVide();
      T val;
      if (tete == queue)
      {
         val = tete.Valeur;
         tete = queue = null;
         return val;
      }
      Noeud p = tete;
      while (p.successeur != queue)
         p = p.successeur;
      val = queue.Valeur;
      queue = p;
      p.successeur = null;
      return val;
   }

Contrairement à PopBack(), la méthode PopFront() est très efficace dans une liste simplement chaînée, étant de complexité constante ().

De nombreuses autres fonctionnalités auraient pu être ajoutées à notre classe, la plus évidente étant sans doute une méthode ou une propriété exposant le nombre d'éléments, qu'il faudrait calculer – complexité linéaire – ou tenir à jour – complexité constante mais répercussions sur la taille de la liste et sur le temps d'exécution des méthodes d'ajout et de suppression d'éléments. Je vous invite à vous amuser à en ajouter quelques-unes.

 
   public T PopFront()
   {
      if (Empty)
         throw new ListeVide();
      T val = tete.Valeur;
      if (tete == queue)
         tete = queue = null;
      else
         tete = tete.successeur;
      return val;
   }
}

Valid XHTML 1.0 Transitional

CSS Valide !