Compléments listes - piles - files

I. Les listes chainées

Lorsque l'implémentation de la liste fait apparaître une chaîne de valeurs, chacune pointant vers la suivante, on dit que la liste est une liste chaînée.

Implémentation choisie

• Une liste est caractérisée par un ensemble de cellules.
• Le lien (on dira souvent le «pointeur») de la variable est un lien vers la première cellule, qui renverra elle-même sur la deuxième, etc.
• Chaque cellule contient donc une valeur et un lien vers la cellule suivante.
• Une liste peut être vide (la liste vide est notée x ou bien None sur les schémas)

Une conséquence de cette implémentation sous forme de liste chaînée est la non-constance du temps d'accès à un élément de liste : pour accéder au 3ème élément, il faut obligatoirement passer par les deux précédents.

À retenir

Dans une liste chaînée, le temps d'accès aux éléments n'est pas constant.

Exemple d'implémentation minimale d'une liste chaînée

Exemple fondateur : implémentation d'une liste chainée en POO

class Cellule :
    def __init__(self, contenu, suivante):
        self.contenu = contenu
        self.suivante = suivante

Cette implémentation rudimentaire permet bien la création d'une liste :

🐍 Script Python

>>> lst = Cellule(3, Cellule(5, Cellule(1,None)))

La liste créée est donc :

Mais plus précisément, on a :

Exercice

ÉnoncéCorrection

Retrouvez comment accéder aux éléments 3, 5 et 1.

🐍 Script Python

>>> lst.contenu
3
>>> lst.suivante.contenu
5
>>> lst.suivante.suivante.contenu
1

On pourra remarquer que l'interface proposée à l'utilisateur n'est pas des plus pratiques...

II. Implémenter une pile avec une liste chaînée

La classe Pile

Il est impératif de comprendre qu'on peut choisir n'importe quelle implémentation de la classe Pile. Il suffit de connaître l'interface.

Par exemple, on choisit celle avec la liste chaînée.

Comprendre, puis tester ci-dessous

###

Lancer Télécharger Téléverser Recharger Sauvegarder

class Cellule :bksl-nl def py-undpy-undinitpy-undpy-und(self, contenu, suivante):bksl-nl self.contenu = contenubksl-nl self.suivante = suivantebksl-nlbksl-nlclass Pile:bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl self.data = Nonebksl-nlbksl-nl def estpy-undvide(self):bksl-nl return self.data == Nonebksl-nlbksl-nl def empile(self, x):bksl-nl self.data = Cellule(x, self.data)bksl-nlbksl-nl def depile(self):bksl-nl v = self.data.contenu # on récupère la valeur à renvoyerbksl-nl self.data = self.data.suivante # on supprime la 1ère cellulebksl-nl return vbksl-nlbksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl """ Le sommet de la pile est à gauche"""bksl-nl s = "sommet -> "bksl-nl c = self.databksl-nl while c != None :bksl-nl s += str(c.contenu)+"|"bksl-nl c = c.suivantebksl-nl return sbksl-nlbksl-nl# Testsbksl-nlp = Pile()bksl-nlprint("On empile")bksl-nlfor i in range(4):bksl-nl p.empile(i)bksl-nl print(p)bksl-nl bksl-nlprint("On dépile")bksl-nlfor i in range(4):bksl-nl p.depile()bksl-nl print(p)bksl-nlbksl-nl# A vous ci-dessous ...bksl-nlbksl-nlbksl-nl

---

---

Crédits

Auteur des listes chainées : Gilles Lassus