Pourquoi SortedList et List utilisent array et pourquoi LinkedList n'est pas beaucoup utilisé?

Question

Dans mon esprit, List est fondamentalement mis en œuvre en utilisant LinkedList, tandis qu'un Array normal est implémenté comme des blocs contigus. J'ai toujours utilisé List car il se trouve dans l'espace de noms Generic et parce que je pensais qu'il utilisait allocation de mémoire dynamique - mais j'avais tort.

Hier, j'ai vu l'implémentation de List en utilisant Reflector et j'ai trouvé qu'il s'agit en réalité d'un tableau de T (T[]). Il y a beaucoup de Array.Copy autour tout en manipulant chaque élément dans le List. Par exemple, lorsque vous utilisez Insert, il va créer une nouvelle mémoire et copier tous les éléments avant/après les éléments insérés. Donc, il me semble que l'utilisation de List est très chère. J'ai aussi vu le SortedList. Je ne suis pas sûr pourquoi un SortedList implémente également un tableau à l'intérieur. Ne pensez-vous pas SortedList serait horrible d'utiliser un tableau que vous avez besoin de trier la liste chaque fois qu'une manipulation mineure à la List se produit?

Je me demande également pourquoi List est si populaire que la plupart des gens l'utilisent plutôt que d'aller LinkedList. Est-ce seulement à cause de la flexibilité de l'indexeur?

Answer 1

Oui, SortedList est O (n) pour les insertions. Utilisez avec précaution.

La principale raison est la conception d'ordinateurs modernes. Le cache CPU est très important parce que la RAM est si lente. La conception du bus mémoire ne pouvait tout simplement pas suivre les avancées rapides de la vitesse d'horloge du processeur. Faire un signal numérique haute fréquence de plus d'un pouce est très difficile.

Un tableau a des performances de cache imbattables, il est très probable que l'élément suivant soit déjà dans le cache lorsque vous l'itérez. Une liste liée donne très peu de chances que c'est le cas, l'élément suivant est essentiellement à une adresse aléatoire. C'est cher, ça bloque le processeur, en attendant que la RAM rattrape. Peut être des centaines de cycles.

Answer 2

Parce que la plupart des collections n'ont pas souvent besoin d'insertions au milieu. Mais ils ont besoin d'un accès direct via un indexeur.

Answer 3

Dans la vraie vie Liste ne remet pas Array.Copy souvent, vous habituellement ajoutez simplement des éléments à un tableau, pas insérer. C'est un but de Liste, contrairement à une liste chaînée. Vous devriez juste choisir une classe de collection appropriée.

Si vous insérez des éléments, utilisez souvent la liste chaînée. Si vous ajoutez généralement des éléments et devez les itérer efficacement, utilisez Liste.

Answer 4

Si vous voulez une collection d'un seul type en mémoire pour lesquels:

1. La collection doit être Growable.
2. L'opération de mutation la plus courante est en ajoutant un élément à la fin de la collection.
3. La récupération rapide par index est essentielle.

puis List<T> est probablement votre meilleur choix. LinkedList<T> peut être un meilleur choix lorsque (2) et (3) ne s'appliquent pas.