Quand utiliser une liste chaînée sur une liste de tableaux / masortingces?

J’utilise beaucoup de listes et de tableaux, mais je n’ai pas encore rencontré de scénario dans lequel la liste de tableaux ne pourrait pas être utilisée aussi facilement, sinon plus, que la liste des liens. J’espérais que quelqu’un pourrait me donner des exemples de quand la liste des liens est nettement meilleure.

Les listes liées sont préférables aux tableaux lorsque:

a) vous avez besoin d’insertions / suppressions en temps constant de la liste (comme dans l’informatique en temps réel où la prévisibilité du temps est absolument critique)

b) vous ne savez pas combien d’éléments seront dans la liste. Avec les tableaux, vous devrez peut-être déclarer et copier de la mémoire si le tableau devient trop volumineux

c) vous n’avez pas besoin d’un access aléatoire à des éléments

d) vous voulez pouvoir insérer des éléments au milieu de la liste (comme une queue prioritaire)

Les tableaux sont préférables lorsque:

a) vous avez besoin d’un access indexé / aléatoire aux éléments

b) vous connaissez le nombre d’éléments dans le tableau à l’avance afin que vous puissiez allouer la quantité de mémoire correcte pour le tableau

c) il faut de la vitesse pour parcourir tous les éléments en séquence. Vous pouvez utiliser des maths de pointeur sur le tableau pour accéder à chaque élément, tandis que vous devez rechercher le noeud en fonction du pointeur de chaque élément de la liste chaînée, ce qui peut entraîner des erreurs de page pouvant entraîner des performances.

d) la mémoire est une préoccupation. Les tableaux remplis prennent moins de mémoire que les listes liées. Chaque élément du tableau n’est que les données. Chaque nœud de liste lié nécessite les données ainsi qu’un (ou plusieurs) pointeurs vers les autres éléments de la liste chaînée.

Les listes de tableaux (comme celles de .Net) vous offrent les avantages des tableaux, mais vous allouent dynamicment des ressources pour que vous n’ayez pas à vous soucier de la taille de la liste. mélanger les éléments autour. Du sharepoint vue des performances, les arraylistes sont plus lents que les tableaux bruts.

Les tableaux ont un access aléatoire O (1), mais ils coûtent vraiment cher à append ou à supprimer des éléments.

Les listes liées sont vraiment peu coûteuses pour append ou supprimer des éléments n’importe où et pour effectuer des itérations, mais l’access aléatoire est O (n).

Pour append aux autres réponses, la plupart des implémentations de liste de tableaux réservent une capacité supplémentaire à la fin de la liste, de sorte que de nouveaux éléments puissent être ajoutés à la fin de la liste dans le temps O (1). Lorsque la capacité d’une liste de tableaux est dépassée, un nouveau tableau plus grand est alloué en interne et tous les anciens éléments sont copiés. Habituellement, le nouveau tableau est deux fois plus grand que l’ancien. Cela signifie qu’en moyenne , l’ajout de nouveaux éléments à la fin d’une liste de tableaux est une opération O (1) dans ces implémentations. Donc, même si vous ne connaissez pas le nombre d’éléments à l’avance, une liste de tableaux peut être plus rapide qu’une liste chaînée pour append des éléments, à condition que vous les ajoutiez à la fin. De toute évidence, l’insertion de nouveaux éléments à des emplacements arbitraires dans une liste de tableaux est toujours une opération O (n).

L’access aux éléments d’une liste de tableaux est également plus rapide qu’une liste chaînée, même si les access sont séquentiels. En effet, les éléments de tableau sont stockés dans une mémoire contiguë et peuvent être facilement mis en cache. Les nœuds de liste liés peuvent potentiellement être dispersés sur plusieurs pages différentes.

Je vous recommande d’utiliser uniquement une liste chaînée si vous savez que vous allez insérer ou supprimer des éléments à des emplacements arbitraires. Les listes de tableaux seront plus rapides pour pratiquement tout le rest.

Algorithm ArrayList LinkedList seek front O(1) O(1) seek back O(1) O(1) seek to index O(1) O(N) insert at front O(N) O(1) insert at back O(1) O(1) insert after an item O(N) O(1) 

ArrayLists est bon pour write-once-read-many ou appenders, mais mauvais pour add / remove de l’avant ou du milieu.

L’avantage des listes apparaît si vous devez insérer des éléments au milieu et que vous ne voulez pas commencer à redimensionner le tableau et à déplacer les éléments.

Vous avez raison en ce sens que ce n’est généralement pas le cas. J’ai eu quelques cas très spécifiques comme ça, mais pas trop.

Ce sont les implémentations les plus courantes de Collection.

ArrayList:

  • insérer / supprimer à la fin généralement O (1) pire des cas O (n)

  • insérer / supprimer au milieu O (n)

  • récupérer n’importe quelle position O (1)

LinkedList:

  • insérer / supprimer dans n’importe quelle position O (1) (notez si vous avez une référence à l’élément)

  • récupérer au milieu O (n)

  • récupérer le premier ou le dernier élément O (1)

Vector: ne l’utilisez pas. C’est une ancienne implémentation similaire à ArrayList mais avec toutes les méthodes synchronisées. Ce n’est pas la bonne approche pour une liste partagée dans un environnement multithreading.

HashMap

insérer / supprimer / récupérer par clé dans O (1)

TreeSet insérer / supprimer / contient dans O (log N)

HashSet insérer / supprimer / contient / taille dans O (1)

Tout dépend du type d’opération que vous effectuez lors de l’itération, toutes les structures de données ont un compromis entre le temps et la mémoire et, selon nos besoins, nous devons choisir le bon DS. Donc, il y a des cas où LinkedList est plus rapide que tableau et vice versa. Considérons les trois opérations de base sur les structures de données.

  • Recherche

Comme array est une structure de données basée sur un index, la recherche dans array.get (index) prendra O (1) alors que la liste chaînée n’est pas un index DS, vous devrez donc parcourir jusqu’à index, où index <= n, Ainsi, le tableau est plus rapide dans la liste des liens lorsque ceux-ci ont un accès aléatoire aux éléments.

Q. Alors, quelle est la beauté derrière cela?

Comme les tableaux sont des blocs de mémoire contigus, de gros blocs seront chargés dans le cache lors du premier access, ce qui accélère l’access aux éléments restants du tableau, tout en accédant aux éléments du tableau. misses, la localité du cache fait référence aux opérations se trouvant dans le cache et s’exécute donc beaucoup plus rapidement que dans la mémoire, essentiellement dans le tableau, nous maximisons les chances d’access aux éléments séquentiels dans le cache. Bien que les listes liées ne soient pas nécessairement dans des blocs de mémoire contigus, rien ne garantit que les éléments apparaissant de manière séquentielle dans la liste sont réellement disposés les uns à côté des autres en mémoire. pour chaque access à un élément de la liste chaînée, cela augmente le temps nécessaire pour y accéder et dégrade les performances. Par conséquent, si nous effectuons davantage d’opérations d’access aléatoire, la recherche sera rapide, comme expliqué ci-dessous.

  • Insertion

Ceci est facile et rapide dans LinkedList, car l’insertion est une opération O (1) dans LinkedList (en Java) par rapport au tableau, considérez le cas où le tableau est plein, nous devons copier le contenu sur le nouveau tableau élément dans ArrayList de O (n) dans le pire des cas, alors que ArrayList doit également mettre à jour son index si vous insérez quelque chose ailleurs que à la fin du tableau, en cas de liste chaînée, vous n’avez pas besoin de le redimensionner mettre à jour les pointeurs.

  • Effacement

Cela fonctionne comme des insertions et mieux dans LinkedList que dans array.

Hmm, Arraylist peut être utilisé dans les cas suivants:

  1. vous n’êtes pas sûr du nombre d’éléments présents
  2. mais vous devez accéder à tous les éléments de manière aléatoire grâce à l’indexation

Par exemple, vous devez importer et accéder à tous les éléments d’une liste de contacts (dont la taille vous est inconnue)

Utiliser la liste chaînée pour le sorting de Radix sur les tableaux et pour les opérations polynomiales.

1) Comme expliqué ci-dessus, les opérations d’insertion et de suppression donnent de bonnes performances (O (1)) dans LinkedList par rapport à ArrayList (O (n)). Par conséquent, s’il est nécessaire d’append et de supprimer fréquemment dans l’application, LinkedList est le meilleur choix.

2) Les opérations de recherche (méthode get) sont rapides dans Arraylist (O (1)) mais pas dans LinkedList (O (n)). Si les opérations d’ajout et de suppression sont moindres, ArrayList serait votre meilleur choix.

Je pense que la principale différence est de savoir si vous devez fréquemment insérer ou supprimer des éléments du haut de la liste.

Avec un tableau, si vous supprimez quelque chose du haut de la liste, la complexité est o (n), car tous les index des éléments du tableau devront être décalés.

Avec une liste chaînée, il s’agit de o (1) car il suffit de créer le nœud, de réaffecter la tête et d’atsortingbuer la référence à la tête précédente.

Lorsque vous insérez ou supprimez fréquemment à la fin de la liste, les tableaux sont préférables car la complexité sera o (1), aucune réindexation n’est requirejse, mais pour une liste chaînée, elle sera o (n) car vous devez partir de la tête au dernier nœud.

Je pense que la recherche dans les listes chaînées et les tableaux sera o (log n) car vous utiliserez probablement une recherche binary.

J’ai fait des parsings comparatives et j’ai constaté que la classe de liste est en fait plus rapide que LinkedList pour l’insertion aléatoire:

 using System; using System.Collections.Generic; using System.Diagnostics; namespace ConsoleApplication1 { class Program { static void Main(ssortingng[] args) { int count = 20000; Random rand = new Random(12345); Stopwatch watch = Stopwatch.StartNew(); LinkedList ll = new LinkedList(); ll.AddLast(0); for (int i = 1; i < count; i++) { ll.AddBefore(ll.Find(rand.Next(i)),i); } Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds); watch = Stopwatch.StartNew(); List list = new List(); list.Add(0); for (int i = 1; i < count; i++) { list.Insert(list.IndexOf(rand.Next(i)), i); } Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds); Console.ReadLine(); } } } 

Il faut 900 ms pour la liste chaînée et 100 ms pour la classe de liste.

Il crée des listes de nombres entiers suivants. Chaque nouvel entier est inséré après un nombre aléatoire qui est déjà dans la liste. Peut-être que la classe List utilise quelque chose de mieux qu'un tableau.

En réalité, la localisation de la mémoire a une énorme influence sur les performances dans le traitement réel.

L’utilisation accrue de la diffusion sur disque dans le traitement des «données volumineuses» par rapport à l’access aléatoire montre à quel point la structuration de votre application peut considérablement améliorer les performances à plus grande échelle.

S’il y a un moyen d’accéder à un tableau de manière séquentielle, c’est de loin le meilleur. Concevoir avec ceci comme objective devrait au moins être considéré si la performance est importante.