On souhaite pouvoir résoudre le problème suivant : stocker
des objets dans une collection, par exemple pour pouvoir les parcourir
afin de leur appliquer un traitement.
Remarque : insérer des objets dans une collection définit
a priori deux ordres sur ces objets : celui dans lequel ils ont été
insérés, et celui dans lequel ils sont restitués.
Le vecteur infini (VecteurInfini.java)
convient si l'ordre de parcours dans la collection correspond à
l'ordre d'insertion (ou son inverse) et si les objets ne sont retirés
que s'ils sont les derniers insérés.
S'il est nécessaire de pouvoir enlever un objet de la collection
facilement, même si il a été inséré depuis
un certain temps, ou s'il doit être possible de l'insérer
à une position quelconque, alors il est nécéssaire
de disposer d'une liste chaînée.
Si toutes les références à une même collection
doivent être affectées lorsqu'on souhaite modifier le contenu
de la collection à partir de l'une quelconque d'entre elles, les
listes fonctionnelles (SList.java)
ne conviennent pas non plus.
Il est en particulier indispensable de disposer d'une entête
de façon à ce que la référence à la
liste ne soit pas changée par une modification. Pour faciliter la
suppression d'un élément, il est recommandé d'utiliser
un double chaînage. L'utilisation d'une cellule marquant la fin de
la liste (sentinelle) permet de limiter les tests de cas particuliers et
ainsi de simplifier le code.
La classe CList utilise la notion de curseur. On considère que
la position courante est située non sur un élément,
mais entre deux. Cela permet de disposer d'une position supplémentaire
et ainsi de ne pas avoir de méthode particulière pour insérer
un élément en tête de liste. Le fait d'avancer le curseur
après insertion a pour effet de ranger les éléments
dans leur ordre d'insertion, si le curseur n'est pas déplacé
autrement. Cela facilite souvent l'utilisation de cette structure, ainsi
que la mise au point des algorithmes qui l'utilisent.