Structure de données : Liste chaînée

16/11/2016 | Tags: structures de données

La liste chaînée est un structure qui contient un nombre dynamique d’éléments. Son principal avantage est que le stockage ne se fait pas en un seul bloc de mémoire. Chaque élément est éparpillé en mémoire et contient l’adresse de l’élément suivant. Il n’y a donc jamais besoin de ré-allouer un énorme bloc de mémoire à l’insertion. L’insertion revient à ajouter un élément en mémoire qui pointe vers la tête de la liste courante.

Par contre il est impossible d’accéder à un élément particulier directement. Il faut parcourir la liste pour cela. De même pour connaître la taille de la liste.

Liste chainée

Liste chaînée de 3 éléments. Source: Wikipédia

Avantages:

  • Ecriture rapide: O(1) (Parfait pour une pile)

Inconvénients:

  • Lecture lente: O(n) (sauf le 1er élément)
  • Ajout d’éléments par l’avant.

Plus de détails sur la page Wikipédia.