Première partie : listes doublement chaînées

On souhaite définir un type de données correspondant à des listes d'éléments de type T (par exemple des listes d'entiers si T = Integer, ou des listes de chaînes de caractères si T = String). Ce type de données doit permettre l'ajout d'éléments en tête et en fin de liste. De plus, on souhaite pouvoir représenter une position dans une liste, de façon à pouvoir la parcourir du début à la fin ou de la fin au début.

Afin de représenter une position dans une liste d'éléments de type T, on définit la classe abstraite suivante :

On peut alors définir la classe abstraite List<T> correspondant à notre type de listes :

Listes doublement chaînées

On souhaite maintenant réaliser une implémentation du type liste à l'aide d'un double chaînage. Une liste doublement chaînée est une liste dont la représentation en mémoire est composée de nœuds, ou maillons, qui portent chacun la valeur d'un élément de la liste ainsi qu'une référence vers le nœud précédent et vers le nœud suivant. Lorsqu'un nœud est le premier ou le dernier d'une suite de nœuds, la référence vers le précédent (resp. vers le suivant) est nulle. Grâce à ce double chaînage, il est possible de naviguer dans une liste du début vers la fin ou de la fin vers le début avec la même complexité. La liste elle-même est un objet qui contient une référence vers son premier nœud et une référence vers son dernier nœud. Si la liste est vide, ces deux références sont nulles. La figure suivante illustre la structure d'une liste chaînée.

Réalisation

Créez une classe LinkedList<T> qui hérite de List<T> et stocke ses éléments dans des maillons. Pour représenter ces maillons, créez une classe Node dans la classe LinkedList<T> ayant les méthodes suivantes :

Deuxième partie : tri par sélection des éléments d'une liste

On souhaite maintenant pouvoir trier les éléments d'une liste en utilisant l'algorithme du tri par sélection donné ci-dessous :

Créez pour cela une classe Sort munie d'une fonction sort (cette fonction ne rend rien, elle trie la liste en place). La fonction sort est paramétrée par le type des éléments de la liste à trier, et elle contraint ce type T à implémenter l'interface Comparable<T>, ce qui signifie que le type T dispose d'une méthode compareTo(T o) permettant de comparer un objet de type T à un autre objet de type T, ce qui est nécessaire pour effectuer le tri. La méthode compareTo rend un résultat négatif si l'objet est inférieur à celui auquel on le compare, 0 si les deux objets sont égaux, et un résultat positif si l'objet est plus grand que celui auquel on le compare.

Pour aller plus loin : application d'opérations aux éléments d'une liste

Dans une nouvelle classe, écrire une fonction qui rend une liste contenant les carrés des éléments d'une liste

Testez-la en calculant la liste des carrés des entiers de 1 à 10.

Faire de même avec une fonction qui calcule la moyenne des éléments d'une liste.

Vous pouvez remarquer que ces deux fonctions ont la même structure : elles parcourent la listes et appliquent une opération à chaque élément pour calculer leur résultat. Dans le premier cas, le résultat final est la liste des résultats de l'application de la fonction {$f:x\mapsto x^2$} à chaque élément de la liste. Dans le second cas, le résultat est la moyenne, calculée par accumulation des valeurs des éléments de la liste.

On définit traditionnellement deux opérations sur les listes qui correspondent à ces exemples :

• map qui applique une fonction à chaque élément d'une liste et rend la liste des résultats. On peut considérer qu'elle construit l'image de la liste par la fonction.
• reduce qui produit un résultat en accumulant les résultats d'une opération appliquée à chaque élément de la liste. La somme et la moyenne des éléments d'une liste sont des exemples de telles reductions.

Ces opérations sur les listes reçoivent en argument une fonction ou une opération, or en Java, les seules choses que l'on peut passer en argument à une méthode sont des valeurs des types de base (int, char, double etc.) et des références sur des objets. Si l'on veut pouvoir passer une fonction en argument à une méthode qui l'applique aux éléments d'une liste, il faut que cette fonction se présente sous la forme d'un objet. Un tel objet doit pouvoir être appliqué à un élément d'une liste, on le supposera donc muni d'une méthode applyTo(T value).

Définissez la classe abstraite suivante :

puis créez une classe Square qui hérite de Function<Integer> et calcule le carré de son argument. Vous pouvez tester votre classe Square avec le code suivant :

Ajoutez à la classe List une méthode :

qui applique f à chaque élément de la liste et rend une liste contenant les résultats.

Utilisez map pour construire la liste des carrés des entiers de 1 à 10 à l'aide de Square.

Opération reduce

On considère maintenant l'opération reduce, dont le résultat peut être d'un type différent de celui des éléments de la liste. Par exemple, la moyenne des éléments d'une liste d'entiers sera un double.

Créez une classe abstraite Operation comme suit : Définissez une classe Mean pour calculer la moyenne des éléments d'une liste d'entiers : Il est bien entendu possible d'ajouter des attributs à la classe Mean afin de stocker les valeurs nécessaires au calcul de la moyenne.

Ajoutez une méthode reduce à la classe List :

qui applique successivement op à tous les éléments de la liste et rend le résultat final de l'opération.

Utilisez reduce pour calculer la moyenne des entiers de 1 à 10 grâce à la classe Mean.