Un pointeur est une plage mémoire destinée à mémoriser une adresse.

En particulier, une référence à un objet peut être vue comme un pointeur sur un objet. Il pointe sur la zone mémoire allouée à cet objet dans le tas.

Dans ce cours, nous allons uniquement considérer des pointeurs de ce type.

Il serait assez difficile et peu pédagogique de présenter les listes dans un cas général abstrait. Nous allons donc baser toutes nos explications sur un exemple qui sera facile à généraliser: une liste de villes. Chaque objet de la liste sera une instance de la classe Ville dont voici la déclaration:

          
class Ville {
  String Nom;
  String CodePostal;
  Ville Suivant;
}

L'attribut Suivant est un pointeur sur une ville. Il sert à mémoriser l'adresse de l'élément suivant de la liste. Dans une suite d'objets, il y aura toujours un attribut jouant ce rôle.

La liste, quand à elle, est définie par l'adresse de son premier élément, puisque l'on peut à partir de là retrouver tous les éléments suivants (nous verrons cela en détails un peu plus loin). La liste peut donc être déclarée comme une référence à un objet de la même classe que ceux de la liste.

Dans notre exemple, on pourrait donc représenter une liste de ville par une variable L de type Ville.

Voici par exemple une liste contenant quatre villes:

L contient l'adresse de la première ville (Ribeauvillé). Le champ Suivant de la première ville contient l'adresse de la seconde (Kingersheim) etc...

Le dernier élément de la liste (Nancy) n'a pas d'élément suivant. Son champ Suivant contient la valeur null, qui, comme nous le savons déjà vu, représente en Java une adresse inexistante.

Remarque: une liste vide se représente simplement par un pointeur de liste égal à null (L == null dans notre exemple).

Pour effectuer un traitement sur chaque élément d'une liste, il est nécessaire de savoir parcourir ses éléments. On utilisera pour cela un pointeur, qui prendra successivement la valeur des adresses de chaque élément de la liste. Voici par exemple comment parcourir une liste de villes dont l'adresse est contenue dans le pointeur L:

Ville p ;
p = L ;
while (null) {

     Traitement de l'élément pointé par p

     p = p.Suivant;
}

Considérons le problème suivant: on dispose d'une liste de villes L et d'une ville pointée par un pointeur p. Comment procéder pour ajouter cet objet dans la liste?

Pour ajouter la ville au début de liste L, il suffit de faire:

  p.Suivant = L ;
  L = p ;

La première affectation 'accroche' l'objet à la liste et la deuxième met à jour l'adresse de la liste qui devient celle de p.

Remarque: cette méthode fonctionne également avec une liste vide. En effet, dans ce cas L vaut null avant l'adjonction. Après l'adjonction, on aura bien une liste d'un élément (p) avec L = p et p.Suivant = null.

La figure suivante illustre l'adjonction en début de liste de la ville Ribeauvillé:

Avant l'adjonction:

• la liste L contient les trois villes Kingersheim, Strasbourg et Nancy.
• L contient l'adresse de l'objet représentant Kingersheim.

Après l'adjonction:

• l'attribut Suivant de l'objet représentant Ribeauvillé contient l'adresse de l'objet représentant Kingersheim.
• L contient l'adresse de l'objet représentant Ribeauvillé.
• L contient donc à présent les quatre villes Ribeauvillé, Kingersheim, Strasbourg et Nancy.

Supposons à présent que la liste n'est pas vide et que l'on souhaite insérer un élément après un certain élément de la liste.

Soit p l'adresse du nouvel élément que l'on souhaite insérer et Curseur, l'adresse de l'élément après lequel on souhaite insérer le nouvel élément. Les instructions suivantes permettent d'obtenir ce que l'on souhaite:

p.Suivant = Curseur.Suivant;
Curseur.Suivant = p;

La figure suivante illustre l'insertion d'une structure représentant Strasbourg, après la structure représentant Kingersheim:

Pour supprimer le premier élément d'une liste, il suffit de remplacer l'adresse de la liste par l'adresse de l'élément qui suit le premier.

Avec notre exemple, cela se traduit par l'instruction suivante:

 L = L.Suivant ;

Remarque: si la liste ne contient qu'un seul élément, ce dernier n'a pas d'élément suivant, mais l'instruction précédente convient également car dans ce cas L.Suivant contient null et la liste devient par conséquent vide.

La figure suivante illustre la suppression du premier élément dans une liste de villes:

Avant la suppression, L pointe sur Ribeauvillé et la liste contient quatre villes.

Après la suppression, L pointe sur la ville qui suivait Ribeauvillé, c'est à dire Kingersheim. De ce fait, elle ne contient plus que les trois villes: Kingersheim, Strasbourg et Nancy.

Supposons à présent que l'on souhaite supprimer l'élément qui suit un certain élément.

Appelons Curseur l'adresse de cet élément. L'instruction suivante permet de supprimer l'élément qui le suit:

 Curseur.Suivant = Curseur.Suivant.Suivant;

La figure suivante illustre ce mécanisme. On supprime ici la ville Strasbourg, en faisant pointer la ville précédente (Kingersheim) sur la ville qui suit Strasbourg(Nancy). De ce fait, Strasbourg n'existe plus dans la liste:

Une autre manière de représenter une liste est de mémoriser deux pointeurs dans chaque élément: un pointeur vers l'élément suivant comme précédemment et un pointeur vers l'élément précédent. On appel ceci une liste doublement chainée.

Avec notre exemple de liste de ville, on pourrait obtenir une liste doublement chainée en ajoutant un nouvel attribut nommé Precedent dans la déclaration de la classe Ville:

          
class Ville {
  String Nom;
  String CodePostal;
  Ville Suivant;
  Ville Precedent;
}

Voici par exemple une liste doublement chainée contenant quatre villes:

La liste est cette fois ci représentée par deux pointeurs LD (adresse du premier élément) et LF (adresse du dernier élément).

Nous ne détaillerons pas ici la réalisation des différentes opérations vues précédemment (adjonction et suppression d'un élément) avec un chainage double. Le lecteur interessé pourra essayer de les réaliser lui même en exercice (voir exercice 2 sur les listes et pointeurs) et s'il n'y arrive pas, consulter le corrigé.

L'intéret du double chainage réside surtout dans l'efficacité de réalisation de certaines opérations. Par exemple, pour insérer un élément, il est inutile de rechercher l'élément précédent, puisqu'on y accède immédiatement via le pointeur associé. Autre avantage: on accède plus rapidement à la fin de la liste et par conséquent, il est plus aisé d'ajouter ou de supprimer un élément en fin de liste. Mais en faisant l'exercice, vous vous rendrez compte que la programmation n'est pas plus aisée ...

Dans le cours sur les tableaux, nous avions vu comment représenter un ensemble de données avec un tableau: le tableau est rempli partiellement avec les données (de même type forcément) jusqu'à un certain indice N définissant la fin des données:

Cette représentation peut également être utilisée pour représenter une liste d'objets. Mais elle présente des inconvénients:

1. Si on ne connait pas à l'avance le nombre d'objets dans la liste, on est obligé de surdimensionner le tableau. On a donc en général un gâchis de place mémoire. Ce n'est pas le cas avec la représentation par pointeurs où la place mémoire utilisée est proportionnelle à la place mémoire occupée par les objets de la liste.
2. L'insertion d'un élément dans la liste est plus complexe puisqu'il faut décaler tous les éléments suivants:
   
   
   
   Cela implique également un temps de calcul plus important. Avec les pointeurs, cette opération peut s'effectuer en deux affectations !
3. Même chose lorsque l'on veut supprimer un élément de position quelconque:
   
   
   
   Avec les pointeurs, cette opération peut s'effectuer en une seule affectation !