Liste chaînée - Définition

Histoire

A 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. Leurs travaux sur les listes chaînées sont publiés dans IRE Transactions on Information Theory en 1956 et plusieurs conférences organisées durant la période 1957 à 1959. La représentation désormais célèbre des listes chaînées, où les nœuds sont des blocs reliés ensemble par des flèches, est publiée en février 1957 dans l'article Programming the Logic Theory Machine. Allen Newell et Herbert Simon se voient décerner en 1975 le Prix Turing pour « leurs contributions fondamentales à l'intelligence artificielle, la psychologie de la compréhension humaine et la manipulation des listes ».

Implémentation

Voici un exemple d'implémentation d'un élément dans le langage Pascal (liste d'entiers simplement chaînée) :

      type liste=^jonction;        jonction=record          contenu:longint;          suivant:liste        end;      

Et un autre exemple en C de l'implémentation d'un élément d'une liste d'entiers doublement chaînée :

      struct liste      {        int donnee;        struct liste * precedent;        struct liste * suivant;      };      

Primitives

On définit un certain nombre de primitives, qui sont des fonctions de test, d'accès en lecture ou en écriture dont la liste permet une exécution efficace.

Il n'existe pas de normalisation pour les primitives de manipulation de liste. Leurs noms sont donc indiqués de manière informelle. Voici la liste des plus couramment utilisées :

• « Placement sur le premier élément » : place l'index sur le premier élément de la liste.
• « Placement sur le dernier élément » : place l'index sur le dernier élément de la liste.
• « Placement sur l'élément suivant » : place l'index sur l'élément qui suit l'élément courant si c'est possible.
• « Placement sur l'élément précédent » : place l'index sur l'élément qui précède l'élément courant si c'est possible.
• « Liste est-elle vide ? » : Retourne vrai si la liste est vide, faux sinon.
• « L'élément courant est-il le premier ? » : Retourne vrai si l'élément courant est le premier élément de la liste, faux sinon.
• « L'élément courant est-il le dernier ? » : Retourne vrai si l'élément courant est le dernier élément de la liste, faux sinon.
• « Nombre d'élément » : renvoie le nombre d'éléments dans la liste.
• « Ajouter en queue » : ajoute un élément après le dernier élément de la liste (efficace seulement pour une liste doublement chaînée).
• « Ajouter en tête » : ajoute un élément avant le premier élément de la liste.
• « Insertion » : insère un élément avant l'élément courant.
• « Remplacement » : Remplace l'élément courant.
• « Suppression » : Supprime l'élément courant.

Ajout d'un élément

Voici la représentation schématique de l'ajout d'un nouvel élément f après un élément e se trouvant dans une liste simplement chaînée. La procédure se fait en deux étapes :

• le successeur de e devient le successeur de f ;
• f devient le successeur de e.