|
Publié le par Chloé MAHALIN

Structure de données

Qu'est-ce qu'une liste chaînée ?

Définition

Une liste chaînée est une liste ou chaque élément connaît son suivant. De ce fait, rajouter un élément à la liste est très facile, puisqu'il suffit d'indiquer au dernier élément quel est le suivant. On comprend donc également que la liste chaînée n'a pas de limite de taille.

liste chaînée

Il existe une autre liste chaînée héritant de la liste chaînée simple : la double liste chaînée. Celle-ci se distingue par le fait que, non seulement chaque élément connaît son successeur, mais en plus, chaque élément connaît son prédécesseur.

Si l'on rencontre ce besoin spécifique, il est aussi possible de faire boucler une liste chaînée sur elle même en indiquant au dernier élément que son successeur est le premier élément.

Avantages et inconvénients

  • Avantages :
    • Structure légère qui prend peu de place en mémoire
    • Taille illimitée
  • Inconvénients :
    • L'insertion au milieu est plus compliquée

_NB : Cette structure nous emmène assez naturellement vers la notion de structure de données arborescente._