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 bienNone
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
1 2 3 4 |
|
Cette implémentation rudimentaire permet bien la création d'une liste :
>>> lst = Cellule(3, Cellule(5, Cellule(1,None)))
La liste créée est donc :
Mais plus précisément, on a :
Exercice
Retrouvez comment accéder aux éléments 3, 5 et 1.
>>> 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
Crédits⚓︎
Auteur des listes chainées : Gilles Lassus
# Tests
(insensible à la casse)(Ctrl+I)
(Ctrl+Clic pour inverser les colonnes)