Listes chaînées

Une liste chaînée est une suite de nœuds où chaque nœud sait où se trouve le suivant. Elle permet d’insérer ou de supprimer un élément sans décaler tous les autres.

Une application de musique garde votre playlist. Vous glissez un titre entre le troisième et le quatrième. Avec un tableau, tous les titres suivants reculeraient d’une case. Ici, deux liens suffisent.

Dans une liste chaînée, les éléments ne sont pas côte à côte en mémoire. Chaque nœud garde sa valeur et un lien vers le nœud suivant.

Le dernier nœud n’a pas de suivant : son lien vaut None. Pour retrouver toute la liste, il suffit de connaître la tête, c’est-à-dire le premier nœud.

Pour fabriquer des nœuds en Python, on écrit une classe. C’est un modèle qui décrit des objets de même forme.

La méthode __init__ s’exécute quand on crée un objet. self désigne l’objet en cours de création. Ici, chaque Noeud a deux attributs : valeur et suivant.

class Noeud:
    def __init__(self, valeur):
        self.valeur = valeur
        self.suivant = None


# Trois nœuds reliés : 10, 20, 30.
a = Noeud(10)
b = Noeud(20)
c = Noeud(30)
a.suivant = b
b.suivant = c

# Parcours : on part de la tête et on suit les liens.
courant = a
while courant is not None:
    print(courant.valeur)
    courant = courant.suivant
# Ajoutez un nœud 40 à la fin, puis relancez.

En C, un nœud est une structure qui range une valeur et un pointeur, c’est-à-dire l’adresse du nœud suivant. Le programme des commandes suivantes relie trois nœuds, les parcourt, puis affiche la taille d’un nœud.

Un entier prend 4 octets et une adresse 8 octets. Le compilateur arrondit à 16 pour aligner l’adresse. Les deux premières commandes n’affichent rien.

printf '%s\n' '#include <stdio.h>' 'struct noeud { int valeur; struct noeud *suivant; };' 'int main(void) {' '  struct noeud c = {30, NULL};' '  struct noeud b = {20, &c};' '  struct noeud a = {10, &b};' '  for (struct noeud *p = &a; p != NULL; p = p->suivant) printf("%d\n", p->valeur);' '  printf("taille du noeud : %d octets\n", (int)sizeof(struct noeud));' '  return 0;' '}' > /tmp/liste.c

gcc -o /tmp/liste /tmp/liste.c

/tmp/liste

Pour insérer un nœud après un autre, on change deux liens. Le nouveau nœud reprend le suivant de l’ancien. Puis l’ancien désigne le nouveau.

Pour supprimer, le nœud d’avant saute par-dessus. Rien ne bouge en mémoire. En revanche, atteindre le nœud numéro k oblige à suivre k liens depuis la tête.

Pour inverser une liste, on la parcourt en retournant chaque lien. Il faut trois repères : precedent, courant et suivant.

On garde d’abord le suivant, sinon la fin de la liste est perdue. Puis le lien de courant désigne precedent. Enfin, on avance d’un nœud.

Écrivez une fonction longueur(tete) qui compte les nœuds. Écrivez ensuite supprimer(tete, valeur), qui retire le premier nœud portant cette valeur.

Pensez au cas où la valeur est dans la tête : la fonction doit alors rendre une autre tête.