Les tableaux stockent les éléments dans des emplacements mémoire contigus, ce qui entraîne des adresses facilement calculables pour les éléments stockés et cela permet un accès plus rapide à un élément à un index spécifique. Les listes chaînées sont moins rigides dans leur structure de stockage et les éléments ne sont généralement pas stockés dans des emplacements contigus, d’où la nécessité de les stocker avec des balises supplémentaires donnant une référence à l’élément suivant. Cette différence dans le schéma de stockage des données décide quelle structure de données serait plus adaptée à une situation donnée.

Schéma de stockage des données d’un tableau

Schéma de stockage des données d’une liste chaînée

Les différences majeures sont énumérées ci-dessous :

• Taille : Puisque les données ne peuvent être stockées que dans des blocs contigus de mémoire dans un tableau, leur taille ne peut pas être modifiée à l’exécution en raison du risque d’écrasement sur d’autres données. Cependant, dans une liste chaînée, chaque nœud pointe vers le suivant de sorte que les données peuvent exister à des adresses dispersées (non contiguës) ; cela permet une taille dynamique qui peut changer au moment de l’exécution.
• Allocation de mémoire : Pour les tableaux au moment de la compilation et au moment de l’exécution pour les listes liées.
• Efficacité de la mémoire : Pour un même nombre d’éléments, les listes chaînées utilisent plus de mémoire car une référence au nœud suivant est également stockée avec les données. Cependant, la flexibilité de la taille dans les listes chaînées peut leur faire utiliser moins de mémoire dans l’ensemble ; ceci est utile lorsqu’il y a une incertitude sur la taille ou qu’il y a de grandes variations dans la taille des éléments de données ; une mémoire équivalente à la limite supérieure de la taille doit être allouée (même si elle n’est pas entièrement utilisée) alors que l’on utilise des tableaux, alors que les listes chaînées peuvent augmenter leur taille progressivement, proportionnellement à la quantité de données.
• Temps d’exécution : Tout élément d’un tableau peut être accédé directement avec son index ; cependant, dans le cas d’une liste chaînée, tous les éléments précédents doivent être traversés pour atteindre un élément quelconque. De plus, une meilleure localité du cache dans les tableaux (en raison de l’allocation de mémoire contiguë) peut améliorer considérablement les performances. Par conséquent, certaines opérations (comme la modification d’un certain élément) sont plus rapides dans les tableaux, tandis que d’autres (comme l’insertion/la suppression d’un élément dans les données) sont plus rapides dans les listes chaînées.

Voici les points en faveur des listes liées.
(1) La taille des tableaux est fixe : Il faut donc connaître à l’avance la limite supérieure du nombre d’éléments. De plus, généralement, la mémoire allouée est égale à la limite supérieure quelle que soit l’utilisation, et dans les utilisations pratiques, la limite supérieure est rarement atteinte.

(2) L’insertion d’un nouvel élément dans un tableau d’éléments est coûteuse car il faut créer une place pour les nouveaux éléments et pour créer de la place, les éléments existants doivent être décalés.

Par exemple, supposons que nous maintenions une liste triée d’identifiants dans un tableau id.

id = .

Et si nous voulons insérer un nouvel ID 1005, alors pour maintenir l’ordre trié, nous devons déplacer tous les éléments après 1000 (à l’exclusion de 1000).

La suppression est également coûteuse avec les tableaux jusqu’à ce que certaines techniques spéciales soient utilisées. Par exemple, pour supprimer 1010 dans id, il faut déplacer tout ce qui se trouve après 1010.

La liste chaînée offre donc les deux avantages suivants par rapport aux tableaux
1) Taille dynamique
2) Facilité d’insertion/suppression

Les listes chaînées présentent les inconvénients suivants :
1) L’accès aléatoire n’est pas autorisé. Nous devons accéder aux éléments séquentiellement en commençant par le premier nœud. On ne peut donc pas faire une recherche binaire avec des listes chaînées.
2) Un espace mémoire supplémentaire pour un pointeur est nécessaire avec chaque élément de la liste.
3) Les tableaux ont une meilleure localité de cache qui peut faire une assez grande différence dans les performances.