……..

14.1 La notion de liste
Une liste est une structure de données qui permet de stocker une séquence d’objets d’un même type. En cela, les listes ressemblent aux tableaux. La séquence d’entiers 3, 7, 2, 4 peut être représentée à la fois sous forme de tableau ou de liste. La notation [3, 7, 2, 4] représentera la liste qui contient cette séquence.
Il y a cependant des différences fondamentales entre listes et tableaux :
– Dans un tableau on a accès immédiat à n’importe quel élément par son indice (accès dit aléatoire), tandis que dans une liste chaînée on a accès aux él éments un après l’autre, à partir du premier élément (accès dit séquentiel).
– Un tableau a une taille fixe, tandis qu’une liste peut augmenter en taille indéfiniment (on peut toujours rajouter un élément à une liste).
14.2 Représentation des listes chaînées en Java
Il y a plusieurs facons de représenter les listes chaînées en Java. L’idée de base est d’utiliser un enchaînement de cellules :
– chaque cellule contient un élément de la liste ;
– chaque cellule contient une référence vers la cellule suivante, sauf la dernière cellule de la liste (qui contient une référence nulle) ;
– la liste donne accès à la première cellule, le reste de la liste est accessible en passant de cellule en cellule, suivant leur enchaînement.
La figure 14.1 illustre cette représentation pour la liste exemple ci-dessus [3, 7, 2, 4].
14.3 Opérations sur les listes chaînées, version itérative
Nous étudierons les opérations les plus importantes sur les listes chaînées, qui seront implémentées comme des méthodes de la classe Liste.
Conformément à leur définition, les listes sont des structures récursives. Par conséquent, les opérations sur les listes s’expriment naturellement par des algorithmes récursifs. En même temps, les listes sont des structures linéaires, parfaitement adaptées à un parcours itératif. Nous allons proposer d’abord une version des classes qui implémentera les méthode de manière itérative, et nous en donnerons ensuite une version récursive.
La représentation de la classe Liste ci-dessous montre sous forme de méthodes les opérations sur listes que nous discuterons.
14.3.1 La classe ElementListe
Nous avons décidé de placer toute la logique des méthodes dans la classe Liste. Ce n’est pas forcément la seule solution, mais le code obtenu sera plus facile à expliquer.
La classe Element Liste est donc réduite à sa plus simple expression : un élément de liste a une valeur, et est suivi d’un autre élément de liste (qui peut être éventuellement null si notre élment est le dernier).
La classe est dotée de plusieurs constructeurs et des accesseurs nécessaires.

………