Aller au contenu

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.

liste chainé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 ❤

Python
1
2
3
4
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 :

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

La liste créée est donc : 3-5-1

Mais plus précisément, on a :

ex2

Exercice

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

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

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Crédits⚓︎

Auteur des listes chainées : Gilles Lassus