Généralités sur les listes chainées

Généralités sur les listes chainées


Lorsque vous créez un algorithme
utilisant des conteneurs, il existe différentes manières de les implémenter, la
façon la plus courante étant les tableaux, que vous connaissez tous. Lorsque
vous créez un tableau, les éléments de celui-ci sont placés de façon contiguë
en mémoire. Pour pouvoir le créer, il vous faut connaître sa taille. Si vous
voulez supprimer un élément au milieu du tableau, il vous faut recopier les
éléments temporairement, ré-allouer de la mémoire pour le tableau, puis le
remplir à partir de l'élément supprimé. En bref, ce sont beaucoup de
manipulations coûteuses en ressources.
Une liste chaînée est différente dans le sens où les éléments de votre liste
sont répartis dans la mémoire et reliés entre eux par des pointeurs. Vous
pouvez ajouter et enlever des éléments d'une liste chaînée à n'importe quel
endroit, à n'importe quel instant, sans devoir recréer la liste entière.

Nous allons essayer de voir ceci plus en détail sur ces schémas :

[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]




Vous avez sur ce schéma la représentation que l'on pourrait faire d'un tableau
et d'une liste chaînée. Chacune de ces représentations possède ses avantages et
inconvénients. C'est lors de l'écriture de votre programme que vous devez vous
poser la question de savoir laquelle des deux méthodes est la plus intéressante.

• Dans un tableau, la taille est
  connue, l'adresse du premier élément aussi. Lorsque vous déclarez un
  tableau, la variable contiendra l'adresse du premier élément de votre
  tableau.
  Comme le stockage est contigu, et la taille de chacun des éléments connue,
  il est possible d'atteindre directement la case i d'un tableau.
  
• Pour déclarer un tableau, il
  faut connaître sa taille.
  
• Pour supprimer ou ajouter un
  élément à un tableau, il faut créer un nouveau tableau et supprimer
  l'ancien. Ce n'est en général pas visible par l'utilisateur, mais c'est ce
  que realloc va souvent faire. L'adresse du premier élément d'un tableau
  peut changer après un realloc, ce qui est tout à fait logique puisque
  realloc n'aura pas forcement la possibilité de trouver en mémoire la place
  nécessaire et contiguë pour allouer votre nouveau tableau. realloc va donc
  chercher une place suffisante, recopier votre tableau, et supprimer
  l'ancien.