Tableau et liste liée

Question

Pourquoi utiliser une liste chaînée plutôt qu'un tableau ?

Le codage d'une liste chaînée est, sans aucun doute, un peu plus difficile que l'utilisation d'un tableau et on peut se demander ce qui justifie cet effort supplémentaire.

Je pense que l'insertion de nouveaux éléments est triviale dans une liste chaînée mais c'est une corvée majeure dans un tableau. Y a-t-il d'autres avantages à utiliser une liste chaînée pour stocker un ensemble de données plutôt qu'un tableau ?

Cette question n'est pas un doublon de cette question parce que l'autre question porte spécifiquement sur une classe Java particulière, alors que la présente question porte sur les structures de données générales.

Answer 1

Une autre bonne raison est que les listes liées se prêtent bien à des implémentations multithread efficaces. La raison en est que les modifications ont tendance à être locales - elles n'affectent qu'un pointeur ou deux pour l'insertion et la suppression dans une partie localisée de la structure de données. Il est donc possible de faire travailler plusieurs threads sur la même liste chaînée. De plus, il est possible de créer des versions sans verrou en utilisant des opérations de type CAS et d'éviter complètement les verrous lourds.

Avec une liste chaînée, les itérateurs peuvent également parcourir la liste pendant que des modifications sont effectuées. Dans le cas optimiste où les modifications n'entrent pas en collision, les itérateurs peuvent continuer sans contention.

Avec un tableau, tout changement qui modifie la taille du tableau est susceptible de nécessiter le verrouillage d'une grande partie du tableau et, en fait, il est rare que cela soit fait sans un verrouillage global sur l'ensemble du tableau de sorte que les modifications deviennent des affaires d'arrêt du monde.

Answer 2

• Il est plus facile de stocker des données de tailles différentes dans une liste chaînée. Un tableau suppose que chaque élément a exactement la même taille.
• Comme vous l'avez mentionné, il est plus facile pour une liste liée de croître organiquement. La taille d'un tableau doit être connue à l'avance, ou recréée lorsqu'elle doit augmenter.
• Pour mélanger une liste liée, il suffit de changer ce qui pointe vers quoi. Le brassage d'un tableau est plus compliqué et/ou prend plus de mémoire.
• Tant que vos itérations se déroulent toutes dans un contexte "foreach", vous ne perdez aucune performance en itération.

Answer 3

Wikipedia a une très bonne section sur les différences.

Les listes chaînées présentent plusieurs avantages par rapport aux tableaux. Les éléments peuvent être insérés dans des listes liées indéfiniment, alors que un tableau finira par se remplir se remplir ou devra être redimensionné, une opération opération coûteuse qui peut même ne pas être possible si la mémoire est fragmentée. De même, un tableau dont de nombreux éléments sont retirés peut devenir inutilement vide ou doit être réduit plus petit.

D'autre part, les tableaux permettent un accès aléatoire aléatoire, alors que les listes liées ne permettent que l'accès séquentiel aux éléments. Les listes singulièrement liées, en fait, ne peuvent être être parcourues dans un seul sens. Cette rend les listes chaînées inadaptées aux applications où il est utile de rechercher rapidement un élément par son index, comme heapsort. L'accès séquentiel sur les tableaux est également plus rapide que sur les listes listes chaînées sur de nombreuses machines en raison de la localité des caches de référence et de données. Les listes liées listes chaînées ne bénéficient pratiquement d'aucun du cache.

Un autre inconvénient des listes chaînées est le stockage supplémentaire nécessaire pour les références, ce qui les rend souvent souvent peu pratique pour les listes de petites données petits éléments de données tels que des caractères ou booléens. Il peut également être lent, et avec avec un allocateur naïf, un gaspillage, de d'allouer de la mémoire séparément pour chaque nouvel élément, un problème généralement problème généralement résolu par l'utilisation de pools de mémoire.

http://en.wikipedia.org/wiki/Linked_list

Answer 4

J'en ajouterai un autre : les listes peuvent servir de purement fonctionnel les structures de données.

Par exemple, vous pouvez avoir des listes complètement différentes qui partagent la même section finale.

a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)

c'est-à-dire :

b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next  

sans avoir à copier les données pointées par l'option a en b y c .

C'est pourquoi ils sont si populaires dans les langages fonctionnels, qui utilisent des variables immuables. prepend y tail Les opérations peuvent être effectuées librement sans avoir à copier les données d'origine - des caractéristiques très importantes lorsque vous traitez les données comme immuables.

Answer 5

La fusion de deux listes liées (en particulier deux listes doublement liées) est beaucoup plus rapide que la fusion de deux tableaux (en supposant que la fusion soit destructive). La première prend O(1), la seconde prend O(n).

EDITAR: Pour clarifier, j'ai voulu dire "fusionner" ici dans le sens non ordonné, pas comme dans "merge sort". Peut-être que "concaténation" aurait été un meilleur mot.