Liste, Pile et FileLes listes chainées
Jusqu’à présent, pour sotcker un ensemble de données, nous utilisions principalement les tableaux et les dictionnaires. Avec les méthodes append() et pop() Python nous fournit des méthodes efficaces pour ajouter ou supprimer un élement en fin de tableau.
En revanche, l'insertion d'un élément en début de tableau nécessite beaucoup plus de travail.
Par exemple inserer l'élément 8 en première position dans le tableau [17,37,45,47,62,85] nécéssite 8 opérations (complixité en ).
Si ce n'est pas génant pour un petit tableau, cela l'est quand le tableau contient des milliers voire des millions d'entrées.
Pour ce genre de situation nous allons voir une structure plus adapté.
À l'origine appelée NSS memory, les listes chaînées ont été conçues dans les années 1955-1956, par Allen Newell, (en) Cliff Shaw et Herbert Simon de RAND Corporation. Les listes chaînées étaient la structure de donnée de base de leur langage (en) Information Processing Language (IPL). IPL était utilisé par ses auteurs pour le développement de plusieurs programmes d'intelligence artificielle, comme Logic Theory Machine, General Problem Solver et un jeu d'échecs.
Définition : liste chainée
Une liste chainée est une structure permettant d'implémenter une liste, c'est-à-dire une séquence finie de valeurs (de même type ou non). Les éléments sont dits chainés car à chaque élément est associé l'adresse mémoire de l'élément suivant de la liste.
Définition : Tête et queue
On appelle tête :
Remarque :
Les données peuvent être de tous types :
Définition : Maillon
Les élèments d'une liste chainée sont généralement appelés Maillon (ou encore chainon). Il contient non seulement des données de type quelconque mais aussi l'adresse mémoire du prochaine élément.
Interface
Il existe plusieurs interfaces possible pour une liste chaînée. Cependant il y a quelques fonctions que l'on retrouve pratiquement toujours. On les appellera les primitives.
Les primitives
- création d'une liste vide
- obtenir la taille la liste
- insertion d'un maillon au début de la liste
- insertion d'un maillon en fin de la liste
- insertion d'un maillon, à n'importe quelle position de la liste
- suppression d'un maillon à n'importe quelle position de la liste
- accéder au n-ième maillon
Explication des différents types d'insertion
Insertion au début Pour insérer une valeur en fin de liste, on créer un maillon ayant la valeur souhaitée et pour suivant le maillon de tête de liste et on le place en tête de liste.
Insertion à la fin
Pour insérer une valeur en fin de liste, on créer un maillon ayant la valeur souhaitée et pour suivant None, on le place ensuite comme suivant du dernier élément de la liste.
Insertion d'un maillon
Pour insérer un maillon à l'indice
Implémentation Python
Pour l'implémentation c'est ici que ça se passe : Accéder au TD
Entrer le code de fin de TD :