Une liste chaînée est une structure de données linéaire composée de nœuds. Chaque nœud possède une valeur et un pointeur vers le nœud suivant. Contrairement aux tableaux contigus en mémoire, les nœuds sont dispersés et reliés par des pointeurs. Les listes chaînées offrent une insertion/suppression en O(1) à une position connue, mais un accès aléatoire en O(n). Elles peuvent être simples (un seul pointeur), doubles (deux pointeurs) ou circulaires (dernier nœud pointe vers la tête).

Définition des classes

Classe pour un nœud de liste simple :

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

Classe pour la liste chaînée :

class ListeChainee:
    def __init__(self):
        self.tete = None
        self.taille = 0

    def est_vide(self):
        return self.taille == 0

    def __len__(self):
        return self.taille

    def __str__(self):
        elements = []
        courant = self.tete
        while courant:
            elements.append(str(courant.valeur))
            courant = courant.suivant
        return " → ".join(elements) + " → None"

Opérations fondamentales

Recherche

def trouver_par_valeur(self, val):
    courant = self.tete
    while courant:
        if courant.valeur == val:
            return courant
        courant = courant.suivant
    return None

def trouver_par_index(self, idx):
    if idx < 0 or idx >= self.taille:
        return None
    courant = self.tete
    for _ in range(idx):
        courant = courant.suivant
    return courant

Insertion

def inserer_en_tete(self, val):
    nouveau = Noeud(val)
    nouveau.suivant = self.tete
    self.tete = nouveau
    self.taille += 1

def inserer_en_queue(self, val):
    nouveau = Noeud(val)
    if self.est_vide():
        self.tete = nouveau
    else:
        courant = self.tete
        while courant.suivant:
            courant = courant.suivant
        courant.suivant = nouveau
    self.taille += 1

def inserer_a_position(self, val, idx):
    if idx < 0 or idx > self.taille:
        raise IndexError("Indice hors limites")
    if idx == 0:
        self.inserer_en_tete(val)
        return
    precedent = self.trouver_par_index(idx - 1)
    nouveau = Noeud(val)
    nouveau.suivant = precedent.suivant
    precedent.suivant = nouveau
    self.taille += 1

Suppression

def supprimer_tete(self):
    if self.est_vide():
        raise IndexError("Suppression impossible sur liste vide")
    val = self.tete.valeur
    self.tete = self.tete.suivant
    self.taille -= 1
    return val

def supprimer_queue(self):
    if self.est_vide():
        raise IndexError("Suppression impossible sur liste vide")
    if self.taille == 1:
        return self.supprimer_tete()
    precedent = self.trouver_par_index(self.taille - 2)
    val = precedent.suivant.valeur
    precedent.suivant = None
    self.taille -= 1
    return val

def supprimer_a_position(self, idx):
    if idx < 0 or idx >= self.taille:
        raise IndexError("Indice hors limites")
    if idx == 0:
        return self.supprimer_tete()
    precedent = self.trouver_par_index(idx - 1)
    val = precedent.suivant.valeur
    precedent.suivant = precedent.suivant.suivant
    self.taille -= 1
    return val

Problème LeetCode 160 : Intersection de deux listes chaînées

Étant donné deux listes chaînées teteA et teteB, trouver leur nœud d'intersectino. L'astuce consiste à utiliser deux pointeurs qui parcourent les deux listes en commutant de liste à la fin, ce qui annule la différence de longueur et les fait se rencontrer au point d'intersection (ou à None s'il n'y a pas d'intersection).

class Solution:
    def getIntersectionNode(self, teteA: Noeud, teteB: Noeud) -> Optional[Noeud]:
        a, b = teteA, teteB
        while a is not b:
            a = a.suivant if a else teteB
            b = b.suivant if b else teteA
        return a

La complexité temporelle est O(m+n) et spatiale O(1). Cette approche simple et élégante illustre la puissance du double pointeur.