Liste doublement chaînée

Liste doublement chaînée

Liste chaînée

Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d'éléments de même type.

L'accès aux éléments d'une liste se fait de manière séquentielle : chaque élément permet l'accès au suivant (contrairement au cas du tableau dans lequel l'accès se fait de manière absolue, par adressage direct de chaque cellule dudit tableau).

Sommaire

Principe

Le principe de la liste chaînée est que chaque élément possède, en plus de la donnée, des pointeurs vers les éléments qui lui sont logiquement adjacents dans la liste. De ce fait, l'usage d'une liste est préconisé pour des raisons de rapidité de traitement, lorsque les insertions et suppressions d'élément en tout point sont relativement plus fréquentes que les accès simples.

En effet, une insertion ou une suppression se font en temps constant car elles ne demandent au maximum que deux accès en écriture. En revanche, l'accès à un élément aléatoirement positionné nécessite le parcours de chaque élément qui sépare l'index de l'élément choisi. Il est donc préférable d'accéder aux éléments séquentiellement.

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[1]. 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[2]. 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 ».

Types de listes chaînées

Il existe plusieurs types de listes chaînées, caractérisés principalement par deux attributs :

  • le chaînage,
  • le cycle.

Chaînage

Liste simplement chaînée

Une liste simplement chaînée, composée de trois éléments ayant respectivement la valeur : 12, 99 et 37.

Comme on le voit sur le schéma ci-contre, deux informations composent chaque élément de la liste chaînée :

  • la valeur associée à l'élément (ou donnée d'exploitation),
  • un pointeur vers l'élément suivant (ou successeur).

Comme un seul élément de la liste est pointé, l'accès se fait uniquement dans un sens.

Liste doublement chaînée

Liste doublement chaînée de quatre éléments.

La différence avec une liste simplement chaînée est que, cette fois-ci, un pointeur vers l'élément précédent (ou prédécesseur) est ajouté. Ainsi l'accès peut se faire indifféremment dans les deux sens : de successeur en successeur, ou de prédécesseur en prédécesseur.

Cette structure est plus coûteuse en mémoire (d'un pointeur par élément de la liste) et en nombre d'instructions pour la mise à jour : une insertion coûte quatre copies de pointeurs contre deux dans le cas d'une liste simplement chaînée.

Par contre, cela permet d'opérer une insertion avant ou après un élément, sans devoir disposer d'un pointeur sur un voisin, là ou une liste simplement chaînée n'autorise une insertion qu'à une seule position par rapport à un élément : en successeur ou (exclusivement) en prédécesseur.

Il est également possible de contrôler l'intégrité d'une liste doublement chaînée en vérifiant le chaînage double.

Cycle

Le cycle est la propriété que présente une liste chaînée de former une boucle (ou chaîne fermée). La notion de début de chaîne ou de fin de chaîne disparaît.

Une liste cyclique (ou circulaire) est créée lorsque le dernier élément possède une référence vers le premier élément (si la liste est doublement chaînée, alors le premier élément possède aussi une référence vers le dernier).

L'utilisation de ce type de liste requiert des précautions pour éviter des parcours indéfinis, par exemple lors d'une recherche vaine d'élément.

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.
Situation initiale
Première étape
Seconde étape

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 * suivant;
  struct liste * precedent;
};

Notes

  1. Proceedings of the Western Joint Computer Conference en 1957 et 1958 et Information Processing en 1959 (première réunion de l'International Conference on Information Processing de l'UNESCO)
  2. Programming the Logic Theory Machine de Allen Newell et Cliff Shaw, Proceedings of the 1957 Western Joint Computer Conference, février 1957

Voir aussi

  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « Liste cha%C3%AEn%C3%A9e ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Liste doublement chaînée de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Liste Chaînée — Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque élément permet …   Wikipédia en Français

  • Liste chainee — Liste chaînée Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque… …   Wikipédia en Français

  • Liste chainée — Liste chaînée Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque… …   Wikipédia en Français

  • Liste chaînée — Une liste chaînée désigne en informatique une structure de données représentant une collection ordonnée et de taille arbitraire d éléments de même type. L accès aux éléments d une liste se fait de manière séquentielle : chaque élément permet …   Wikipédia en Français

  • Liste (informatique) — Cet article concerne l utilisation du mot liste en informatique, pour une définition plus générale du mot liste, voir le Wiktionnaire. En informatique, une liste est une structure de données permettant de regrouper des données de manière à… …   Wikipédia en Français

  • Tas de Fibonacci — En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la …   Wikipédia en Français

  • Tas de fibonacci — En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la …   Wikipédia en Français

  • Données struturées — Structure de données En informatique, une structure de données est une structure logique destinée à contenir des données, afin de leur donner une organisation permettant de simplifier leur traitement. Une structure de données implémente… …   Wikipédia en Français

  • Structuration des données — Structure de données En informatique, une structure de données est une structure logique destinée à contenir des données, afin de leur donner une organisation permettant de simplifier leur traitement. Une structure de données implémente… …   Wikipédia en Français

  • Structure de donnees — Structure de données En informatique, une structure de données est une structure logique destinée à contenir des données, afin de leur donner une organisation permettant de simplifier leur traitement. Une structure de données implémente… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”