Liste chainee simple

Une liste chainee, c'est comme un train : chaque wagon (noeud) contient une donnée et un lien vers le wagon suivant. Le dernier wagon ne pointe vers rien (None).

Contrairement a une liste Python qui stocke ses éléments dans un tableau contigu en mémoire, une liste chainee peut avoir ses noeuds eparpilles n'importe ou. L'avantage : insérer un élément au debut est O(1), alors que c'est O(n) avec une liste classique (il faut decaler tous les éléments).

Tu vas créer deux classes :

Noeud : chaque noeud a une valeur et un attribut suivant qui pointe vers le noeud suivant (ou None).

ListeChainee : elle a un attribut tete qui pointe vers le premier noeud, et trois méthodes :
- ajouter_debut(val) : insère un noeud en tete
- ajouter_fin(val) : insère un noeud a la fin
- vers_liste() : retourne une liste Python avec toutes les valeurs

Exemple :
lc = ListeChainee()
lc.ajouter_fin(1)
lc.ajouter_fin(2)
lc.ajouter_debut(0)
lc.vers_liste() renvoie [0, 1, 2]

Tests (3/4)

Ajouter fin

lc = ListeChainee()
lc.ajouter_fin(1)
lc.ajouter_fin(2)
lc.ajouter_fin(3)
assert lc.vers_liste() == [1, 2, 3]

Ajouter debut

lc = ListeChainee()
lc.ajouter_fin(2)
lc.ajouter_debut(1)
assert lc.vers_liste() == [1, 2]

Mixte

lc = ListeChainee()
lc.ajouter_fin(1)
lc.ajouter_fin(2)
lc.ajouter_debut(0)
assert lc.vers_liste() == [0, 1, 2]

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

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

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

    def ajouter_debut(self, val):
        nouveau = Noeud(val)
        nouveau.suivant = self.tete
        self.tete = nouveau

    def ajouter_fin(self, val):
        nouveau = Noeud(val)
        if self.tete is None:
            self.tete = nouveau
            return
        courant = self.tete
        while courant.suivant is not None:
            courant = courant.suivant
        courant.suivant = nouveau

    def vers_liste(self):
        résultat = []
        courant = self.tete
        while courant is not None:
            résultat.append(courant.valeur)
            courant = courant.suivant
        return résultat

← File (queue) avec collections.deque Table de hachage simplifiee →

solution.py

Bravo!

Liste chainee simple

Tests (3/4)

Indices (3 disponibles)

Solution officielle