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

class Maillon:
   def __init__(self, v = None):
      self.val = v     # None pour désigner une liste chaînée vide
      self.suiv = None # Pas de maillon suivant

M1, M2 = Maillon(14), Maillon(8)
M1.suiv = M2

    def est_vide(self): 
        """ Renvoie True si la liste chaînée 
            définie par le Maillon de tête self
            est vide """ 
        return self.v is None

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

def get_maillon_indice(M, i): 
   """ Renvoie Maillon d'indice i dans la liste de tête M """ 
   j = 0
   m = M
   while j < i:
      j += 1
      m = m.suiv 
   return m

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

def ajouter_fin(M, nM): 
    """ Ajoute le maillon nM en queue de la liste de tête M """ 
    m = M 
    while m.suiv is not None:
        m = m.suiv
    # m est le DERNIER Maillon !
    m.suiv = nM

def ajouter_apres(M0, nM): 
    """ Ajoute le maillon nM après le maillon M0 """
    nM.suiv = M0.suiv
    M0.suiv = nM

def supprimer_debut(M): 
    """ Supprime le 1er maillon de la liste de tête M et le renvoie """
    suiv = M.suiv
    M.val, suiv.vam = suiv.val, M.val # permutation des valeurs
    M.suiv = suiv.suiv
    suiv.suiv = None   # on isole le Maillon supprimé
    return suiv

def supprimer_fin(M): 
    """ Supprime le dernier maillon de la liste de tête M et le renvoie """ 
    m = M
    while m.suiv.suiv is not None:
       m = m.suiv
    # m est l'AVANT DERNIER Maillon !
    fin = m.suiv # on garde une référence du Maillon supprimé de la liste
    m.suiv = None
    return fin

def supprimer_apres(M0): 
    """ Supprime le maillon situé après le maillon M0 et le renvoie """ 
    s = M0.suiv
    M0.suiv = M0.suiv.suiv
    return s

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

class ListeChainee:
   def __init__(self):
      self.tete = None # de type Maillon si la liste n'est pas vire

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

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

M2 = (8, None) 
M1 = (14, M2)
L = M1

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