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 :
public abstract class Position<T> {
//@ Get the value which is at this position in the list
public abstract T getValue();
//@ Set the value at this position in the list
public abstract void setValue(T value);
//@ Get the position just after this position in the list
public abstract Position<T> getNextPosition();
//@ Get the position just before this position in the list
public abstract Position<T> getPreviousPosition();
//@ Remove the object at this position in the list
public abstract void remove();
}
On peut alors définir la classe abstraite List<T> correspondant à notre type de listes :
public abstract class List<T> implements Iterable<T> {
//@ Add an item to the end of this list
public abstract void append(T item);
//@ Add an item at the beginning of this list
public abstract void prepend(T item);
//@ Get the number of items in this list
public abstract int size();
//@ Get the position of the first item in this list
public abstract Position<T> getFirstPosition();
//@ Get the position of the last item in this list
public abstract Position<T> getLastPosition();
}
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 :
private class Node extends Position<T> {
//@ The value which is held by the node
private T value;
//@ Reference to the next Node in the list
private Node next;
//@ Reference to the previous Node in the list
private Node prev;
//@ Build a new Node
public Node(T value, Node previous, Node next) {
...
}
//@ Get the value held by this Node
@Override
public T getValue() {
...
}
//@ Set the value held by this Node
@Override
public void setValue(T value) {
...
}
//@ Get the Node preceding this Node
@Override
public Node getPreviousPosition() {
...
}
//@ Get the Node next to this Node
@Override
public Node getNextPosition() {
...
}
//@ Create a Node holding <code>value</code> just before this node
public Node linkBefore(T value) {
...
}
//@ Create a Node holding <code>value</code> just after this node
public Node linkAfter(T value) {
...
}
//@ Remove this Node from the chain
@Override
public void remove() {
...
}
}
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 :
operation selectionSort: List<T> l →
pour p variant du debut de l à la fin de l
min_node ← p;
pour q variant du nœud suivant p à la fin de l
si valeur de q < valeur de min_node
min_node ← q;
fin_si
fin_pour
permuter les entiers portés par les nœuds min_node et p
fin_pour
fin_operation
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.
public class Sort {
//@ Selection sort on lists
public static <T extends Comparable<T>> void sort(List<T> l) {
...
}
}
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
public class SquareList {
public static List<Integer> square(List<Integer> l) {
...
}
}
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 :
mapqui 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.reducequi 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 :
public abstract class Function<T> {
public abstract T applyTo(T value);
}
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 :
public static void main(String args[]) {
System.out.println(new Square().applyTo(2));
}
Ajoutez à la classe List une méthode :
public List<T> map(Function<T> f) { ... }
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 :
public abstract class Operation<R,T> {
public abstract void applyTo(T value); // applique l'opération à un éléments
public abstract R getResult(); // donne le résultat final de l'opération
}
Définissez une classe Mean pour calculer la moyenne des éléments d'une liste d'entiers :
public class Mean extends Operation<Double, Integer> {
public void applyTo(Integer value) { ... }
public abstract Double getResult() { ... }
}
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 :
public <R> reduce(Operation<R,T> op) { ... }
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.