Comparatif d'implémentations, classe ListeEntiers

Ce qui suit montre une implémentation simple d'une classe ListeEntiers, représentant une liste simplement chaînée d'entiers, dans trois langages distincts soit Java, C# et C++. Chacune a ses forces, faiblesses et caractéristiques diverses; l'idée ici est de mettre en relief les similitudes et différences entre elles, pas de critiquer ou d'encenser l'une ou l'autre.

Nous débuterons par un comparatif côte à côte des trois implémentations, suite à quoi nous reviendrons sur les détails de chacune (détail de la version C#, détail de la version C++, détail de la version Java).

Comparatif côte à côte

Placées côte à côte, les implémentations que nous examinerons dans ces trois langages vont comme suit.

Implémentation C# Implémentation C++ Implémentation Java 
using System;
namespace ListeEntiers
{
   public class ListeVide
      : ApplicationException
   {
   }
   public sealed class ListeEntiers
   {
      private sealed class Noeud
      {
         public Noeud Succ { get; set; } = null;
         public int Valeur
         {
            get; private set;
         }
         public Noeud(int val)
         {
            Valeur = val;
         }
         public Noeud (Noeud n)
         {
            Valeur = n.Valeur;
         }
      }
      private Noeud Tete { get; set; } = null;
      private Noeud Fin { get; set; } = null;
      public bool Vide
      {
         get { return Tete == null; }
      }
      public int Taille { get; private set; } = 0;
      public void Vider()
      {
         Tete = Fin = null;
         Taille = 0;
      }
      public ListeEntiers()
      {
      }
      private ListeEntiers(ListeEntiers lst)
      {
         for (Noeud p = lst.Tete; p != null; p = p.Succ)
            Ajouter(p.Valeur);
      }
      public ListeEntiers Dupliquer() =>
         new ListeEntiers(this);
      public void Ajouter(int val)
      {
         Noeud p = new Noeud(val);
         if (Vide)
            Tete = Fin = p;
         else
         {
            Fin.Succ = p;
            Fin = p;
         }
         ++Taille;
      }
      public void Inverser()
      {
         Noeud nouvelleTete = null,
               nouvelleFin = null;
         if (Tete != null) // cas particulier pour se charger de nouvelleFin
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleFin = nouvelleTete = p;
            p = Tete;
            Tete = Tete.Succ;
         }
         while (Tete != null)
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleTete = p;
            p = Tete;
            Tete = Tete.Succ;
         }
         Tete = nouvelleTete;
         Fin = nouvelleFin;
      }
      public int Extraire()
      {
         if (Vide)
            throw new ListeVide();
         Noeud p = Tete;
         Tete = Tete.Succ;
         int val = p.Valeur;
         if (p == Fin) Fin = null;
         --Taille;
         return val;
      }
   }
   class Program
   {
      static void Main(string[] args)
      {
         const int NB_ENTIERS = 10;
         ListeEntiers lst = new ListeEntiers();
         for (int i = 0; i < NB_ENTIERS; i++)
            lst.Ajouter(i + 1);
         ListeEntiers lstInv = lst.Dupliquer();
         lstInv.Inverser();
         int nbÉléments = lstInv.Taille;
         for (int i = 0; i < nbÉléments; i++)
            System.Console.Write("{0} ", lstInv.Extraire());
         System.Console.WriteLine(); ;
         for (int i = 0; i < nbÉléments; i++)
            System.Console.Write("{0} ", lst.Extraire());
         System.Console.WriteLine(); ;
      }
   }
}
 
#include <utility>
class ListeEntiers final {
   struct Noeud final {
      Noeud *succ{};
      int val;
      Noeud(int val) noexcept : val{ val } {
      }
      Noeud(const Noeud &n) noexcept : val{ n.val } {
      }
   };
   Noeud *tete {};
   Noeud *fin {};
   int nelems {};
public:
   bool est_vide() const noexcept {
      return !tete;
   }
   int taille() const noexcept {
      return nelems;
   }
   class ListeVide { };
   void clear() noexcept {
      for(auto p = tete; p;) {
         auto q = p->succ;
         delete p;
         p = q;
      }
      nelems = 0;
      tete = fin = nullptr;
   }
   ListeEntiers() = default;
   ListeEntiers(const ListeEntiers &lst) {
      for (auto p = lst.tete; p; p = p->succ)
         ajouter(p->val);
   }
   ListeEntiers(ListeEntiers && lst) noexcept
      : tete{ std::exchange(lst.tete, nullptr) },
        fin{ std::exchange(lst.fin, nullptr) },
        nelems{ std::exchange(lst.nelems, 0) } {
   }
   void swap(ListeEntiers &lst) noexcept {
      using std::swap;
      swap(tete,lst.tete);
      swap(fin,lst.fin);
      swap(nelems,lst.nelems);
   }
   ListeEntiers& operator=(const ListeEntiers &lst) {
      ListeEntiers{ lst }.swap(*this);
      return *this;
   }
   ListeEntiers& operator=(ListeEntiers && lst) noexcept {
      if(this == &lst) return *this;
      clear();
      tete = std::exchange(lst.tete, nullptr);
      fin = std::exchange(lst.fin, nullptr);
      nelems = std::exchange(lst.nelems, 0);
      return *this;
   }
   ~ListeEntiers() {
      clear();
   }
   void ajouter(int val) {
      auto p = new Noeud{val};
      if (est_vide())
         tete = fin = p;
      else {
         fin->succ = p;
         fin = p;
      }
      ++nelems;
   }
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      int val = p->val;
      if (p == fin) fin = {};
      delete p;
      --nelems;
      return val;
   }
   // attention : version de qualité très discutable
   void inverser() {
      Noeud *nouvelleTete = {},
            *nouvelleFin = {};
      if (tete) { // cas particulier pour se charger de nouvelleFin
         auto p = new Noeud{*tete};
         p->succ = nouvelleTete;
         nouvelleFin = nouvelleTete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelleTete;
         nouvelleTete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelleTete;
      fin = nouvelleFin;
   }
};
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter (i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lst.extraire() << " ";
   cout << endl;
}
 
class ListeVide extends Exception {
}
public final class ListeEntiers {
   private final class Noeud {
      public Noeud succ = null;
      private int valeur;
      public int getValeur() {
         return valeur;
      }
      public Noeud(int val) {
         valeur = val;
      }
      public Noeud (Noeud n) {
         valeur = n.getValeur();
      }
   }
   private Noeud tete = null;
   private Noeud fin = null;
   private int taille = 0;
   public boolean estVide() {
      return tete == null;
   }
   public int getTaille() {
      return taille;
   }
   public ListeEntiers() {
   }
   private ListeEntiers(ListeEntiers lst) {
      for (Noeud p = lst.tete; p != null; p = p.succ) {
         ajouter(p.getValeur());
      }
   }
   public ListeEntiers dupliquer() {
      return new ListeEntiers(this);
   }
   public void ajouter(int val) {
      Noeud p = new Noeud(val);
      if (estVide()) {
         tete = fin = p;
      } else {
         fin.succ = p;
         fin = p;
      }
      ++taille;
   }
   public void inverser() {
      Noeud nouvelleTete = null,
            nouvelleFin = null;
      if (tete != null) { // cas particulier pour se charger de nouvelleFin
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleFin = nouvelleTete = p;
         p = tete;
         tete  = tete.succ;
      }
      while (tete != null) {
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleTete = p;
         p = tete;
         tete = tete.succ;
      }
      tete = nouvelleTete;
      fin = nouvelleFin;
   }
   public int extraire() throws ListeVide {
      if (estVide()) {
         throw new ListeVide();
      }
      Noeud p = tete;
      tete = tete.succ;
      int val = p.getValeur();
      if (p == fin) {
         fin = null;
      }
      --taille;
      return val;
   }
   public static void main(String[] args) {
      final int NB_ENTIERS = 10;
      ListeEntiers lst = new ListeEntiers();
      for (int i = 0; i < NB_ENTIERS; i++)
         lst.ajouter(i + 1);
      ListeEntiers lstInv = lst.dupliquer();
      lstInv.inverser();
      try {
         int nbÉléments = lstInv.getTaille();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstInv.extraire() + " ");
         }
         System.out.println();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lst.extraire() + " ");
         }
         System.out.println();
      } catch (ListeVide lv) {
         System.err.println("Très, très suspect...");
      }
   }
}
Exécution, implémentation C# Exécution, implémentation C++ Exécution, implémentation Java 
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
 
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10
 
10 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 10

Ne vous fiez pas au nombre de lignes dans chaque cas pour évaluer la complexité relative de chacune des implémentations. J'ai disposé le code dans le respect (à ma connaissance) des pratiques de chaque langage, et certains (C#, par exemple) tendent à générer du code plus « vertical » alors que d'autres (Java, par exemple) mènent à du code plus « horizontal », ne serait-ce que dû aux usages quant à la disposition des accolades.

Quelques notes d'ordre général :

Pour le reste, un sympathique constat nous attend : les similitudes sont de loin plus nombreuses que les différences!

Discussion de l'implémentation C#

Le détail de notre implémentation à l'aide du langage C# suit.

Avec C#, tout type d'exception doit dériver, directement ou non, de la classe Exception, et la plupart des exceptions des programmes que nous écrivons devraient dériver plus précisément de la classe ApplicationException. C'est ce que nous faisons ici.

 
using System;
namespace ListeEntiers
{
   public class ListeVide
      : ApplicationException
   {
   }

La classe ListeEntiers est terminale. Son interface ne se prête pas à spécialisation sans effets adverses.

 
   public sealed class ListeEntiers
   {

Une liste simplement chaînée se compose typiquement de noeuds, tels que chacun connaît son successeur. Ainsi, de manière minimaliste, connaître le premier noeud (la tête) de la liste donne un accès indirect à tous les autres.

Notre classe Noeud est interne à la classe ListeEntiers, comme il se doit (le noeud est un détail d'implémentation et ne concerne pas le code client). Pour cette raison, les accès à la valeur (en lecture, du moins) et au successeur sont publics, n'étant en pratique accessibles qu'aux noeuds et à la liste.

La valeur d'un Noeud est immuable une fois le noeud construit.

Puisque nous sommes ici en C#, les propriétés sont de mise.

N'étant pas vouée à être spécialisée, cette classe est aussi terminale.

Remarquez que le constructeur paramétrique initialise le sucesseur d'un Noeud à null, et que le constructeur « de copie » ne copie pas le successeur; organiser les noeuds est le travail de la liste; les noeuds ont pour mandat d'entreposer les données, pas de s'organiser entre eux.

 
      private sealed class Noeud
      {
         public Noeud Succ { get; set; } = null;
         public int Valeur
         {
            get; private set;
         }
         public Noeud(int val)
         {
            Valeur = val;
         }
         public Noeud(Noeud n)
         {
            Valeur = n.Valeur;
         }
      }

Les états de notre ListeEntiers sont au nombre de trois, soit :

  • Tete, une référence sur le premier Noeud de la liste, pour usage interne seulement
  • Fin, une référence sur le dernier Noeud de la liste, aussi pour usage interne seulement – ceci permet certaines optimisations, en particulier lors des ajouts à la fin, mais n'est pas à strictement parler nécessaire pour définir une liste simplement chaînée), et
  • Taille, un compteur du nombre de noeuds dans la liste (ceci aussi permet d'optimiser le calcul du nombre d'éléments dans la liste, sans toutefois être nécessaire en tant que tel), accessible publiquement en consultation mais pour usage interne en ce qui a trait aux modifications

S'ajoute à ces propriétés la propriété en lecture seulement Vide, prédicat qui s'avère seulement si la liste est vide et dont l'implémentation est de complexité constante, donc .

 
      private Noeud Tete { get; set; } = null;
      private Noeud Fin { get; set; } = null;
      public bool Vide
      {
         get { return Tete == null; }
      }
      public int Taille { get; private set; } = 0;
      public void Vider()
      {
         Tete = Fin = null;
         Taille = 0;
      }

Une ListeEntiers par défaut sera une liste vide : sa téte et sa fin sont toutes deux des références nulles, et son nombre d'éléments est zéro.

 
      public ListeEntiers()
      {
      }

J'ai implémenté un « constructeur de copie » privé, donc un constructeur acceptant en paramètre lst, une référence sur une ListeEntiers, et faisant de la ListeEntiers en cours de construction une copie, noeud par noeud, de la liste lst.

L'optimisation permise par l'utilisation d'une référence sur le dernier noeud, qui donne à la méthode Ajouter() sa complexité constante, , fait de ce constructeur une opération raisonnable (complexité linéaire, ). Sans cette optimisation, la méthode Ajouter() serait de complexité linéaire (il faudrait parcourir la liste entière à chaque fois pour trouver le dernier élément avant de lui apposer un successeur), et ce constructeur serait alors de complexité quadratique, , ce qui la rendrait inutilisable en pratique.

Si la ListeEntiers avait été vouée à une spécialisation polymorphique, ce constructeur aurait été protégé et la duplication d'une ListeEntiers aurait été faite par clonage. J'ai choisi ici d'offrir le constructeur de copie privé et d'exposer un service public de duplication, la méthode Dupliquer(), parce que le recours au constructeur de copie ne fait pas partie des usages en C#.

 
      private ListeEntiers(ListeEntiers lst)
      {
         for (Noeud p = lst.Tete; p != null; p = p.Succ)
            Ajouter(p.Valeur);
      }
      public ListeEntiers Dupliquer() =>
         new ListeEntiers(this);

La méthode Ajouter() permet de réaliser une insertion en fin de liste. Cette opération se réalise en temps constant dû à la connaissance a priori du dernier Noeud de la liste; si nous n'avions pas cette information, alors il faudrait de prime abord trouver le dernier noeud de la liste, une opération coûteuse.

Notez que l'on ajoute bel et bien un int à la liste, pas un Noeud. Les noeuds sont des outils organisationnels internes, pas un élément de l'interface d'une ListeEntiers.

 
      public void Ajouter(int val)
      {
         Noeud p = new Noeud(val);
         if (Vide)
            Tete = Fin = p;
         else
         {
            Fin.Succ = p;
            Fin = p;
         }
         ++Taille;
      }

La méthode Inverser() est la plus complexe du lot en termes d'écriture (sa complexité algorithmique, elle, est linéaire, ). Il s'agit d'un mutateur : elle inverse l'ordre dans lequel les noeuds de la liste apparaissent, ce qui n'est pas nécessairement une pratique recommandable – il serait en général préférable de retourner une nouvelle liste dont les éléments seraient dans l'ordre inverse de ceux de la liste originale, et de laisser cette dernière inchangée.

Pour une liste de éléments, cette implémentation fait allocations dynamiques de mémoire pour des noeuds. Ici, la présence d'un ramasse-miettes permet de ne pas se préoccuper de la libération des noeuds « périmés », mais accroît la probabilité qu'une collecte d'ordures soit provoquée pendant l'exécution de la méthode, surtout si la liste comprend un nombre élevé de noeuds.

 
      public void Inverser()
      {
         Noeud nouvelleTete = null,
               nouvelleFin = null;
         if (Tete != null) // cas particulier pour se charger de nouvelleFin
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleFin = nouvelleTete = p;
            p = Tete;
            Tete = Tete.Succ;
         }
         while (Tete != null)
         {
            Noeud p = new Noeud(Tete);
            p.Succ = nouvelleTete;
            nouvelleTete = p;
            p = Tete;
            Tete = Tete.Succ;
         }
         Tete = nouvelleTete;
         Fin = nouvelleFin;
      }

La méthode Extraire() élimine un Noeud de la liste et retourne la valeur que ce Noeud entreposait. C'est aussi une méthode de complexité constante, ou . Cette implémentation dépend d'un ramasse-miettes pour assurer le nettoyage des noeuds périmés

 
      public int Extraire()
      {
         if (Vide)
            throw new ListeVide();
         Noeud p = Tete;
         Tete = Tete.Succ;
         int val = p.Valeur;
         if (p == Fin) Fin = null;
         --Taille;
         return val;
      }
   }

Le programme de test accomplit la tâche attendue, soit tester de manière directe ou indirecte la plupart des services de la classe ListeEntiers.

 
   class Program
   {
      static void Main(string[] args)
      {
         const int NB_ENTIERS = 10;
         ListeEntiers lst = new ListeEntiers();
         for (int i = 0; i < NB_ENTIERS; i++)
            lst.Ajouter(i + 1);
         ListeEntiers lstInv = lst.Dupliquer();
         lstInv.Inverser();
         int nbÉléments = lstInv.Taille;
         for (int i = 0; i < nbÉléments; i++)
            System.Console.Write("{0} ", lstInv.Extraire());
         System.Console.WriteLine(); ;
         for (int i = 0; i < nbÉléments; i++)
            System.Console.Write("{0} ", lst.Extraire());
         System.Console.WriteLine(); ;
      }
   }
}

Discussion de l'implémentation C++

Le détail de notre implémentation à l'aide du langage C++ suit. Notez que dans le code ci-dessous, les clauses throw() devraient être remplacées par des clauses noexcept, mais le compilateur à ma disposition quand j'ai rédigé le tout n'était pas suffisamment à jour pour supporter ce mécanisme de C++ 11.

La classe ListeEntiers est terminale. Son interface ne se prête pas à spécialisation sans effets adverses.

 
#include <utility>
class ListeEntiers final {

Une liste simplement chaînée se compose typiquement de noeuds, tels que chacun connaît son successeur. Ainsi, de manière minimaliste, connaître le premier noeud (la tête) de la liste donne un accès indirect à tous les autres.

Notre classe Noeud est interne à la classe ListeEntiers, comme il se doit (le noeud est un détail d'implémentation et ne concerne pas le code client). Pour cette raison, les accès à la valeur (en lecture, du moins) et au successeur sont publics, n'étant en pratique accessibles qu'aux noeuds et à la liste.

La valeur d'un Noeud devrait être immuable une fois le noeud construit; ici, ce sera assuré par discipline, mais il aurait été possible de faire de val un attribut privé auquel les accès passent par un accesseur pour garantir cela.

N'étant pas vouée à être spécialisée, cette classe est aussi terminale.

Remarquez que le constructeur paramétrique initialise le sucesseur d'un Noeud à nullptr, et que le constructeur de copie ne copie pas le successeur; organiser les noeuds est le travail de la liste; les noeuds ont pour mandat d'entreposer les données, pas de s'organiser entre eux.

 
   struct Noeud final {
      Noeud *succ {};
      int val;
      Noeud (int val) noexcept : val{ val } {
      }
      Noeud(const Noeud &n) noexcept : val{ n.val } {
      }
   };

Les attributs de notre ListeEntiers sont au nombre de trois, soit :

  • tete, un pointeur sur le premier Noeud de la liste
  • fin, un pointeur sur le dernier Noeud de la liste – ceci permet certaines optimisations, en particulier lors des ajouts à la fin, mais n'est pas à strictement parler nécessaire pour définir une liste simplement chaînée), et
  • nelems, un compteur du nombre de noeuds dans la liste (ceci aussi permet d'optimiser le calcul du nombre d'éléments dans la liste, sans toutefois être nécessaire en tant que tel)

Deux services clés de la liste sont des accesseurs de premier ordre, soit est_vide(), prédicat qui s'avère seulement si la liste est vide, et taille(), qui donne accès au nombre de noeuds dans la liste. Ces deux fonctions sont de complexité constante, donc . Si j'avais voulu conformer ce conteneur au standard du langage, je les aurais nommées empty() et size() respectivement.

 
   Noeud *tete {};
   Noeud *fin {};
   int nelems {};
public:
   bool est_vide() const noexcept {
      return !tete;
   }
   int taille() const noexcept {
      return nelems;
   }

Avec C++, tout type peut servir pour signaler une exception. L'usage est de définir un type dont le nom représente le problème à souligner (ici ListeEntiers::ListeVide) pour éliminer les nombreux ennuis associés aux messages qu'ont les exceptions « traditionnelles » (internationalisation, langue).

 
   class ListeVide { };
   void clear() noexcept {
      for(auto p = tete; p;) {
         auto q = p->succ;
         delete p;
         p = q;
      }
      nelems = 0;
      tete = fin = nullptr;
   }

Une ListeEntiers par défaut sera une liste vide : sa téte et sa fin sont toutes deux des pointeurs nuls, et son nombre d'éléments est zéro.

 
   ListeEntiers() = default;

J'ai implémenté un constructeur de copie public, comme il se doit pour les classes concrètes en C++.

L'optimisation permise par l'utilisation d'un pointeur sur le dernier noeud, qui donne à la méthode ajouter() sa complexité constante, , fait de ce constructeur une opération raisonnable (complexité linéaire, ). Sans cette optimisation, la méthode ajouter() serait de complexité linéaire (il faudrait parcourir la liste entière à chaque fois pour trouver le dernier élément avant de lui apposer un successeur), et ce constructeur serait alors de complexité quadratique, , ce qui la rendrait inutilisable en pratique.

 
   ListeEntiers(const ListeEntiers &lst) {
      for (auto p = lst.tete; p; p = p->succ)
         ajouter(p->val;
   }

Les autres éléments de la Sainte-Trinité sont comme présentés à droite, et respectent les usages les plus répandus :

  • Méthode swap() de complexité et ne levant pas d'exception
  • Destructeur en temps linéaire et ne levant pas d'exception (il pourrait être plus rapide encore; j'ai choisi la simplicité ici), et
  • Un opérateur d'affectation implémenté selon l'idiome d'affectation sécuritaire

Ces fonctions n'ont pas de réelle contrepartie dans les langages où l'on ne manipule pas directement les objets (et dont font partie C# et Java). Les finaliseurs de C# ne sont pas vraiment des équivalents des destructeurs de C++.

 
   void swap(ListeEntiers &lst) noexcept {
      using std::swap;
      swap(tete,lst.tete);
      swap(fin,lst.fin);
      swap(nelems,lst.nelems);
   }
   ListeEntiers& operator=(const ListeEntiers &lst) {
      ListeEntiers{ lst }.swap(*this);
      return *this;
   }
   ~ListeEntiers() {
      while(!est_vide())
         extraire();
   }

Les consignes ne le demandaient pas, mais j'ai implémenté la sémantique de mouvement dans la classe ListeEntiers. Après tout, cette méthode est simple à écrire, ne lève pas d'exceptions, s'exécute en temps constant, et permet de nombreuses optimisations. Ce serait fou de s'en passer!

 
   ListeEntiers(ListeEntiers && lst) noexcept
      : tete{ std::exchange(lst.tete, nullptr) },
        fin{ std::exchange(lst.finm nullptr) },
        nelems{ std::exchange(lst.nelems, 0) } {
   }
   ListeEntiers& operator=(ListeEntiers && lst) noexcept{
      if (this == &lst) return *this;
      clear();
      tete = std::exchange(lst.tete, nullptr);
      fin = std::exchange(lst.fin, nullptr);
      nelems = std::exchange(lst.nelems, 0);
      return *this;
   }

La méthode ajouter() permet de réaliser une insertion en fin de liste. Cette opération se réalise en temps constant dû à la connaissance a priori du dernier Noeud de la liste; si nous n'avions pas cette information, alors il faudrait de prime abord trouver le dernier noeud de la liste, une opération coûteuse.

Notez que l'on ajoute bel et bien un int à la liste, pas un Noeud. Les noeuds sont des outils organisationnels internes, pas un élément de l'interface d'une ListeEntiers.

 
   void ajouter(int val) {
      auto p = new Noeud{val};
      if (est_vide())
         tete = fin = p;
      else {
         fin->succ = p;
         fin = p;
      }
      ++nelems;
   }

La méthode extraire() élimine un Noeud de la liste et retourne la valeur que ce Noeud entreposait. C'est aussi une méthode de complexité constante, ou . Cette implémentation assure elle-même le nettoyage des noeuds périmés

 
   int extraire() {
      if (est_vide()) throw ListeVide{};
      auto p = tete;
      tete = tete->succ;
      int val = p->val;
      if (p == fin) fin_ = {};
      delete p;
      --nelems;
      return val;
   }

La méthode inverser() est la plus complexe du lot en termes d'écriture (sa complexité algorithmique, elle, est linéaire, ). Il s'agit d'un mutateur : elle inverse l'ordre dans lequel les noeuds de la liste apparaissent, ce qui n'est pas nécessairement une pratique recommandable – il serait en général préférable de retourner une nouvelle liste dont les éléments seraient dans l'ordre inverse de ceux de la liste originale, et de laisser cette dernière inchangée.

Pour une liste de éléments, cette implémentation fait allocations dynamiques de mémoire pour des noeuds. Chaque noeud est détruit une fois son utilité chose du passé, puisque C++ ne suppose pas un ramasse-miettes. Une alternative aurait été d'utiliser des pointeurs intelligents, mais dans ce cas la gestion à faire était suffisamment simple pour que je me limite à de vulgaires pointeurs bruts.

Cette fonction est hautement perfectible.

 
   void inverser() {
      Noeud *nouvelleTete = {},
            *nouvelleFin = {};
      if (tete) { // cas particulier pour se charger de nouvelleFin
         auto p = new Noeud{*tete};
         p->succ = nouvelleTete;
         nouvelleFin = nouvelleTete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      while (tete) {
         auto p = new Noeud{*tete};
         p->succ = nouvelleTete;
         nouvelleTete = p;
         p = tete;
         tete = tete->succ;
         delete p;
      }
      tete = nouvelleTete;
      fin = nouvelleFin;
   }
};

Le programme de test accomplit la tâche attendue, soit tester de manière directe ou indirecte la plupart des services de la classe ListeEntiers.

 
// ...
#include <iostream>
int main() {
   using namespace std;
   const int NB_ENTIERS = 10;
   ListeEntiers lst;
   for (int i = 0; i < NB_ENTIERS; i++)
      lst.ajouter (i + 1);
   ListeEntiers lstInv = lst;
   lstInv.inverser();
   const int NB_ELEMENTS = lstInv.taille();
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lstInv.extraire() << " ";
   cout << endl;
   for (int i = 0; i < NB_ELEMENTS; i++)
      cout << lst.extraire() << " ";
   cout << endl;
}

Discussion de l'implémentation Java

Le détail de notre implémentation à l'aide du langage Java suit.

Avec Java, tout type d'exception doit dériver, directement ou non, de la classe Exception. C'est ce que nous faisons ici.

 
class ListeVide extends Exception {
}

La classe ListeEntiers est terminale. Son interface ne se prête pas à spécialisation sans effets adverses.

 
public final class ListeEntiers {

Une liste simplement chaînée se compose typiquement de noeuds, tels que chacun connaît son successeur. Ainsi, de manière minimaliste, connaître le premier noeud (la tête) de la liste donne un accès indirect à tous les autres.

Notre classe Noeud est interne à la classe ListeEntiers, comme il se doit (le noeud est un détail d'implémentation et ne concerne pas le code client). Pour cette raison, les accès à la valeur (en lecture, du moins) et au successeur sont publics, n'étant en pratique accessibles qu'aux noeuds et à la liste.

La valeur d'un Noeud est immuable une fois le noeud construit.

Notez que dû au rôle circonscrit de cette classe et au fait qu'elle ne peut être utilisée qu'à l'interne par ListeEntiers, j'ai laissé l'attribut succ public (et oui, dans ce cas, c'est légitime).

Remarquez que le constructeur paramétrique initialise le sucesseur d'un Noeud à null, et que le constructeur « de copie » ne copie pas le successeur; organiser les noeuds est le travail de la liste; les noeuds ont pour mandat d'entreposer les données, pas de s'organiser entre eux.

 
   private final class Noeud {
      public Noeud succ = null;
      private int valeur;
      public int getValeur() {
         return valeur;
      }
      public Noeud(int val) {
         valeur = val;
      }
      public Noeud (Noeud n) {
         valeur = n.getValeur();
      }
   }

Les attributs de notre ListeEntiers sont au nombre de trois, soit :

  • tete, une référence sur le premier Noeud de la liste
  • fin, une référence sur le dernier Noeud de la liste – ceci permet certaines optimisations, en particulier lors des ajouts à la fin, mais n'est pas à strictement parler nécessaire pour définir une liste simplement chaînée), et
  • taille, un compteur du nombre de noeuds dans la liste (ceci aussi permet d'optimiser le calcul du nombre d'éléments dans la liste, sans toutefois être nécessaire en tant que tel)

Deux services clés de la liste sont des accesseurs de premier ordre, soit estVide(), prédicat qui s'avère seulement si la liste est vide, et getTaille(), qui donne accès au nombre de noeuds dans la liste. Ces deux fonctions sont de complexité constante, donc .

 
   private Noeud tete = null;
   private Noeud fin = null;
   private int taille; = 0
   public boolean estVide() {
      return tete == null;
   }
   public int getTaille() {
      return taille;
   }

Une ListeEntiers par défaut sera une liste vide : sa téte et sa fin sont toutes deux des références nulles, et son nombre d'éléments est zéro.

 
   public ListeEntiers() {
   }

J'ai implémenté un « constructeur de copie » privé, donc un constructeur acceptant en paramètre lst, une référence sur une ListeEntiers, et faisant de la ListeEntiers en cours de construction une copie, noeud par noeud, de la liste lst.

L'optimisation permise par l'utilisation d'une référence sur le dernier noeud, qui donne à la méthode ajouter() sa complexité constante, , fait de ce constructeur une opération raisonnable (complexité linéaire, ). Sans cette optimisation, la méthode ajouter() serait de complexité linéaire (il faudrait parcourir la liste entière à chaque fois pour trouver le dernier élément avant de lui apposer un successeur), et ce constructeur serait alors de complexité quadratique, , ce qui la rendrait inutilisable en pratique.

Si la ListeEntiers avait été vouée à une spécialisation polymorphique, ce constructeur aurait été protégé et la duplication d'une ListeEntiers aurait été faite par clonage. J'ai choisi ici d'offrir le constructeur de copie privé et d'exposer un service public de duplication, la méthode dupliquer(), parce que le recours au constructeur de copie ne fait pas partie des usages en Java.

 
   private ListeEntiers(ListeEntiers lst) {
      for (Noeud p = lst.tete; p != null; p = p.succ) {
         ajouter(p.getValeur());
      }
   }
   public ListeEntiers dupliquer() {
      return new ListeEntiers(this);
   }

La méthode ajouter() permet de réaliser une insertion en fin de liste. Cette opération se réalise en temps constant dû à la connaissance a priori du dernier Noeud de la liste; si nous n'avions pas cette information, alors il faudrait de prime abord trouver le dernier noeud de la liste, une opération coûteuse.

Notez que l'on ajoute bel et bien un int à la liste, pas un Noeud. Les noeuds sont des outils organisationnels internes, pas un élément de l'interface d'une ListeEntiers.

 
   public void ajouter(int val) {
      Noeud p = new Noeud(val);
      if (estVide()) {
         tete = fin = p;
      } else {
         fin.succ = p;
         fin = p;
      }
      ++taille;
   }

La méthode inverser() est la plus complexe du lot en termes d'écriture (sa complexité algorithmique, elle, est linéaire, ). Il s'agit d'un mutateur : elle inverse l'ordre dans lequel les noeuds de la liste apparaissent, ce qui n'est pas nécessairement une pratique recommandable – il serait en général préférable de retourner une nouvelle liste dont les éléments seraient dans l'ordre inverse de ceux de la liste originale, et de laisser cette dernière inchangée.

Pour une liste de éléments, cette implémentation fait allocations dynamiques de mémoire pour des noeuds. Ici, la présence d'un ramasse-miettes permet de ne pas se préoccuper de la libération des noeuds « périmés », mais accroît la probabilité qu'une collecte d'ordures soit provoquée pendant l'exécution de la méthode, surtout si la liste comprend un nombre élevé de noeuds.

 
   public void inverser() {
      Noeud nouvelleTete = null,
            nouvelleFin = null;
      if (tete != null) { // cas particulier pour se charger de nouvelleFin
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleFin = nouvelleTete = p;
         p = tete;
         tete  = tete.succ;
      }
      while (tete != null) {
         Noeud p = new Noeud(tete);
         p.succ = nouvelleTete;
         nouvelleTete = p;
         p = tete;
         tete = tete.succ;
      }
      tete = nouvelleTete;
      fin = nouvelleFin;
   }

La méthode extraire() élimine un Noeud de la liste et retourne la valeur que ce Noeud entreposait. C'est aussi une méthode de complexité constante, ou . Cette implémentation dépend d'un ramasse-miettes pour assurer le nettoyage des noeuds périmés.

La clause throws ListeVide est obligatoire en Java si extraire() est susceptible de lever ListeVide.

 
   public int extraire() throws ListeVide {
      if (estVide()) {
         throw new ListeVide();
      }
      Noeud p = tete;
      tete = tete.succ;
      int val = p.getValeur();
      if (p == fin) {
         fin = null;
      }
      --taille;
      return val;
   }

Le programme de test accomplit la tâche attendue, soit tester de manière directe ou indirecte la plupart des services de la classe ListeEntiers. Remarquez que le code Java doit insérer une forme de gestion d'exception lors d'appels à extraire(), même s'il est évident à l'oeil nu qu'aucune exception ne sera levée ici.

 
   public static void main(String[] args) {
      final int NB_ENTIERS = 10;
      ListeEntiers lst = new ListeEntiers();
      for (int i = 0; i < NB_ENTIERS; i++)
         lst.ajouter(i + 1);
      ListeEntiers lstInv = lst.dupliquer();
      lstInv.inverser();
      try {
         int nbÉléments = lstInv.getTaille();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lstInv.extraire() + " ");
         }
         System.out.println();
         for (int i = 0; i < nbÉléments; i++) {
            System.out.print(lst.extraire() + " ");
         }
         System.out.println();
      } catch (ListeVide lv) {
         System.err.println("Très, très suspect...");
      }
   }
}

Conclusion

Vous remarquerez que les ressemblances sont beaucoup plus nombreuses que les divergences. Personnellement, j'ai écrit l'une des versions, et la traduction dans les autres langages s'est faite en quelques minutes chaque fois. Les plus importantes différences ont trait à la sémantique d'accès (directe ou indirecte) et à ses conséquences : en C++, écrire la Sainte-Trinité; en Java et en C#, compenser le partage implicite par une duplication manuelle.

Valid XHTML 1.0 Transitional

CSS Valide !