Une liste chaînée étiquetée (en anglais labelled linked list), appelée désormais liste, est définie récursivement de la façon suivante : une liste est soit vide, soit formée d'une étiquette et d'une liste. De façon analogue aux arbres binaires, une liste chaînée étiquetée non vide peut être implémentée à l'aide d'une classe à deux champs, contenant respectivement une étiquette (objet d'un type Object quelconque) et une référence à une liste :
class ListeChainee {
Object étiquette;
ListeChainee suivant;
ListeChainee(Object étiquette, ListeChainee suivant) {
if (étiquette == null)
throw new NullPointerException();
this.étiquette = étiquette;
this.suivant = suivant;
}
// méthodes
}
Une liste non vide sera représentée par une référence à une instance de ListeChainee, et la liste vide par la valeur null. Tout traitement d'une liste doit d'abord tester si elle est vide.
La liste de la figure 2.6 est désignée par la référence p définie par :
ListeChainee p =
new ListeChainee(
new Integer(2),
new ListeChainee(
new Integer(1),
new ListeChainee(
new Integer(0),
null)));
La structure de liste chaînée permet d'implémenter le type abstrait Table, en étiquetant les listes par des instances du type Association. On fait de la classe ListeChainee un membre statique privé de TableParListe, de manière à cacher les détails d'implémentation. La recherche séquentielle d'une cellule par sa clé dans une liste se fait de façon très classique par une boucle for qui parcourt la liste ; la condition d'exécution est l != null, où l désigne une ListeChainee ; l'instruction d'itération remplace un lien par le lien suivant.
class TableParListe implements Table {
static class Association {
// ...
}
private static class ListeChainee {
// ...
}
private ListeChainee liste;
public boolean insérer(Object clé, Object information) {
liste =
new ListeChainee(new Association(clé, information), liste);
return true;
}
public Object rechercher(Object clé) {
return rechercher(clé, liste);
}
Object rechercher(Object clé, ListeChainee l) {
if (l == null) {
return null;
} else if (((Association)l.étiquette).clé.equals(clé)) {
return ((Association)l.étiquette).information;
} else {
return rechercher(clé, l.suivant);
}
}
public boolean supprimer(Object clé)
{
if (liste == null) {
return false;
}
else if (((Association)liste.étiquette).clé.equals(clé)) {
liste = liste.suivant;
return true;
} else {
return supprimer(clé, liste.suivant, liste);
}
}
boolean supprimer(Object clé,
ListeChainee l,
ListeChainee pré) {
if (l == null) {
return false;
} else if (((Association)l.étiquette).clé.equals(clé)) {
pré.suivant = l.suivant;
return true;
} else {
return supprimer(clé, l.suivant, l);
}
}
}
Il est facile de formuler la recherche de façon itérative :
Object rechercherIter(Object clé) {
for (ListeChainée l = liste; l!=null; l = l.suivant) {
if (((Association)l.étiquette).clé.equals(clé)) {
return ((Association)l.étiquette).information;
}
}
return null;
}
L'API Java 2 offre l'interface List et une implémentation LinkedList au moyen de listes doublement chaînées, qui dispose de deux champs (privés) de type LinkedList, l'un vers le prédecesseur dans la liste, l'autre vers le successeur.
La recherche dichotomique ne fonctionne plus pour ce type de liste, car on ne peut plus déterminer en temps constant le milieu d'une liste chaînée, mais seulement en temps linéaire. Pour conserver l'idée de la recherche dichotomique et garantir un coût logarithmique à toutes les opérations (insertion, recherche et suppression), il faut implémenter les tables par des arbres. En fait, on peut obtenir encore mieux que le coût logarithmique : le coût constant!