Listes chaînées

Une liste chaînée (ou liste liée) est une structure de données composées d’une séquence d’éléments de liste.

Chaque enregistrement d’une liste chaînée est souvent appelé élément , nœud ou maillon.

La tête d’une liste est son premier nœud. La queue d’une liste peut se référer soit au reste de la liste après la tête, soit au dernier nœud de la liste.

Le champ de chaque nœud qui contient l’adresse du nœud suivant ou précédent est généralement appelé lien ou pointeur. Le contenu est placé dans un ou plusieurs autres champs appelés données, informations ou valeur.

Liste chaînée

Chaque élément (ou maillon) M de la liste est composé :

• d’un contenu utile M.val (de n’importe quel type),
• d’un pointeur M.suiv pointant vers l’élément suivant de la séquence.

Le dernier élément de la liste possède un pointeur M.suiv vide :

Une liste chainée L est entièrement définie par son maillon de tête L.tete, c’est à dire l’adresse de son premier maillon.

On peut également lui ajouter un attribut L.cur pour mémoriser l’adresse d’un maillon « courant ».

Interface (primitives)

Il n’existe pas de normalisation pour les primitives de manipulation de liste; les plus fréquentes sont :

• est_vide(L) : renvoie vrai si la liste L est vide,
• taille(L) : renvoie le nombre d’éléments de la liste L,
• get_dernier_maillon(L) : renvoie le dernier élément de la liste,
• get_maillon_indice(L, i) : renvoie le maillon d’indice i ,
• ajouter_debut(L, d) : ajoute un maillon d au début de la liste L,
• ajouter_fin(L, d) : ajoute un maillon d à la fin de la liste L,
• inserer_apres(L, i, M) : insert un maillon à l’indice i,
• supprimer_apres(L, M) : supprime le maillon qui suit le maillon M,
• …

Insertion d’un maillon

Pour insérer un maillon nM après un maillon M, il faut :

1. Faire pointer le pointeur nM.suiv vers M.suiv
2. Faire pointer le pointeur M.suiv vers nM

Suppression d’un maillon

Pour supprimer le maillon suivant un maillon M, il faut :

1. Faire pointer le pointeur M.suiv vers M.suiv.suiv
2. Détruire (effacer de la mémoire) le maillon M.suiv

Remarque : dans certains langages disposants d’un dispositif de ramasse-miettes (comme Python par exemple), le simple fait de ne plus être référencé détruit l’objet Maillon. Dans d’autres langages, il faut explicitement détruire l’objet, et par conséquent, en garder une référence avant l’étape 1.

Implémentation

Python

On peut implémenter un maillon de liste chaînée en Python à l’aide d’une classe Maillon :

class Maillon:
   def __init__(self):
      self.val = None
      self.suiv = None # Pas de maillon suivant

Son attribut suiv est de type Maillon, ou bien vaut None si le maillon est le dernier de la liste.

Et une liste chaînée s’implémente par une classe ListeC :

class ListeC:
   def __init__(self):
      self.tete = None # Liste vide

Son attribut tete est de type Maillon, ou bien vaut None si la liste est vide.

On peut alors créer une liste ainsi :

L = ListeC()
M1, M2 = Maillon(), Maillon()
M1.suiv = M2
L.tete = M1

On implémente la fonction est_vide(L) simplement de cette manière :

def est_vide(L):
   return L.tete is None

def tailleListe(L): 
   """ Renvoie le nombre de Maillons de la liste L """ 
   m = L.tete
   l = 0 
   while m is not None:
      l += 1
      m = m.suiv
   return l

def get_maillon_indice(L, i): 
   """ Renvoie Maillon d'indice i dans la liste L """ 
   j = 0
   m = L.tete 
   while j < i:
      j += 1
      m = m.suiv 
   return m

def ajouter_debut(L, nM): 
   """ Ajoute le maillon nM en tête de la liste L """ 
   nM.suiv = L.tete
   L.tete = nM

def ajouter_fin(L, nM): 
   """ Ajoute le maillon nM en queue de la liste L """ 
   m = L.tete 
   while m.suiv is not None:
      m = m.suiv
   m.suiv = nM

def ajouter_apres(L, M, nM): 
   """ Ajoute le maillon M après celui d'indice i dans la liste L """
   nM.suiv = M.suiv
   M.suiv = nM

def supprimer_debut(L): 
   """ Supprime le 1er maillon de la liste L et le renvoie """
   t = L.tete
   L.tete = L.suiv
   return t

def supprimer_fin(L): 
   """ Supprime le dernier maillon de la liste L et le renvoie """ 
   m = L.tete
   while m.suiv.suiv is not None:
      m = m.suiv
   m.suiv = None
   return m

def supprimer_apres(L, M): 
   """ Supprime le maillon de la liste L situé après le maillon M et le renvoie """ 
   s = M.suiv
   M.suiv = M.suiv.suiv
   return s

Récursivité

La structure même d’une liste chainée est récursive : chaque maillon d’une liste chainée est le début d’une nouvelle liste chainée.

C, C++

On peut implémenter un maillon de liste chaînée en C à l’aide d’un objet structure Maillon  :

struct Maillon {
   float val;
   Maillon *suiv;
}

Son attribut suiv est de type Maillon.

Remarque : *suiv est de type structure Maillon, tandis que suiv est un pointeur, c’est à dire l’adresse de *suiv.

Et une liste chaînée s’implémente par une structure ListeC :

struct ListeC {
   Maillon *tete;
}

Son attribut tete est de type Maillon.

On peut alors créer une liste ainsi :

ListeC L;
Maillon M1, M2;
M1.suiv = &M2;
L.tete = &M1;

Remarque : &M1 signifie « adresse de M1« 

Liste doublement chaînée

Chaque élément (ou maillon) M de la liste est composé :

• d’un contenu utile M.val (de n’importe quel type),
• d’un pointeur M.suiv pointant vers l’élément suivant de la séquence,
• d’un pointeur M.prec pointant vers l’élément précédent de la séquence.

Le dernier élément de la liste possède un pointeur .suiv vide : 

et le premier un pointeur .prec vide : 

Interface

Il n’existe pas de normalisation pour les primitives de manipulation de liste; les plus fréquentes sont :

• est_vide(L) : renvoie vrai si la liste est vide,
• taille(L) : renvoie le nombre d’éléments de la liste,
• get_dernier_maillon(L) : renvoie le dernier élément de la liste,
• get_maillon_indice(L, i) : renvoie le maillon d’indice i,
• ajouter_debut(L, d) : ajoute un élément d au début de la liste,
• ajouter_fin(L, d) : ajoute un élément d à la fin de la liste,
• inserer_apres(L, i, M) : insert un maillon M à l’indice i,
• supprimer_apres(L, M) : supprime le maillon suivant le maillon M,
• …

Remarque : dans les exemples de fonction précédents, M est de type Maillon alors que l’élément d est de type quelconque. Mais les fonctions pourraient accepter les deux types : si on passe un objet qui n’est pas un maillon, le maillon devrait alors être automatiquement créé.

Implémentation