Les 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 O(n)). 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.



Allen Newell, Cliff Shaw et Herbert Simon sont aussi parmis les premièrs à travailler sur l'intelligence artificiel.



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 : d'une liste chaînée.

On appelle queue :


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 n, on créer un maillon ayant la valeur souhaitée et pour suivant le maillon à l'indice n et on change le lien du maillon à l'indice n-1 pour qu'il point vers le nouveau maillon.


    Implémentation Python

    Pour l'implémentation c'est ici que ça se passe : Accéder au TD