Quand utiliser une liste liée sur une liste de tableaux / tableaux?

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

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

1. vous avez besoin d'insertions / suppressions en temps constant de la liste (comme dans le calcul en temps réel où la prévisibilité temporelle est absolument essentielle)

2. vous ne savez pas combien d'articles seront dans la liste. Avec les tableaux, vous devrez peut-être re-déclarer et copier la mémoire si le tableau devient trop grand

3. vous n'avez besoin d'un accès aléatoire à aucun élément

4. vous voulez pouvoir insérer des éléments au milieu de la liste (comme une file d'attente prioritaire)

Les tableaux sont préférables lorsque:

1. vous avez besoin d'un accès indexé / aléatoire aux éléments

2. vous connaissez le nombre d'éléments dans le tableau à l'avance afin de pouvoir allouer la bonne quantité de mémoire pour le tableau

3. vous avez besoin de vitesse pour parcourir tous les éléments en séquence. Vous pouvez utiliser les mathématiques du pointeur sur le tableau pour accéder à chaque élément, alors que vous devez rechercher le nœud en fonction du pointeur de chaque élément de la liste liée, ce qui peut entraîner des erreurs de page pouvant entraîner des problèmes de performances.

4. la mémoire est une préoccupation. Les tableaux pleins 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ée nécessite les données ainsi qu'un (ou plusieurs) pointeurs vers les autres éléments de la liste liée.

Les listes de tableaux (comme celles de .Net) vous offrent les avantages des tableaux, mais allouent dynamiquement des ressources pour vous afin que vous n'ayez pas à vous soucier trop de la taille de la liste et que vous puissiez supprimer des éléments à n'importe quel index sans aucun effort ou mélanger les éléments. En termes de performances, les arraylists sont plus lents que les tableaux bruts.

Les tableaux ont un accès aléatoire O (1), mais sont très coûteux d'ajouter ou de supprimer des éléments.

Les listes liées sont vraiment bon marché pour ajouter ou supprimer des éléments n'importe où et pour itérer, mais l'accès aléatoire est O (n).

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)

Les ArrayLists sont bons pour l'écriture une fois-lecture-plusieurs ou les ajouts, mais mauvais pour ajouter / supprimer du début ou du milieu.

Pour ajouter aux autres réponses, la plupart des implémentations de listes de tableaux réservent une capacité supplémentaire à la fin de la liste afin que de nouveaux éléments puissent être ajoutés à la fin de la liste en 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 fait le double de la taille de 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. Ainsi, 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 ajouter des éléments, tant que vous les ajoutez à 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'accès aux éléments d'une liste de tableaux est également plus rapide qu'une liste chaînée, même si les accès sont séquentiels. En effet, les éléments du 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 de nombreuses pages différentes.

Je recommanderais uniquement d'utiliser une liste lié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 à peu près tout le reste.

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, ce n'est généralement pas le cas. J'ai eu quelques cas très spécifiques comme ça, mais pas trop.

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 en fonction de nos besoins, nous devons choisir le bon DS. Il y a donc des cas où LinkedList est plus rapide que array et vice versa. Considérez les trois opérations de base sur les structures de données.

• Recherche

Étant donné que le tableau est une structure de données basée sur un index, la recherche de array.get (index) prendra O (1) temps tandis que la liste liée n'est pas l'index DS, vous devrez donc parcourir jusqu'à l'index, où index <= n, n est la taille de la liste liée, Ainsi, le tableau est plus rapide dans la liste liée lorsque vous avez un accès aléatoire aux éléments.

Q. Alors, quelle est la beauté derrière tout ça?

Comme les tableaux sont des blocs de mémoire contigus, de gros morceaux d'entre eux seront chargés dans le cache lors du premier accès, ce qui rend l'accès relativement rapide aux éléments restants du tableau, autant que nous accédons aux éléments dans la localité de référence du tableau augmente également donc moins de capture manque, la localité du cache fait référence aux opérations qui se trouvent dans le cache et s'exécutent donc beaucoup plus rapidement que dans la mémoire, fondamentalement En tableau, nous maximisons les chances d'accès séquentiel aux éléments dans le cache. Bien que les listes liées ne soient pas nécessairement dans des blocs contigus de mémoire, il n'y a aucune garantie que les éléments qui apparaissent séquentiellement dans la liste sont réellement disposés les uns à côté des autres en mémoire, cela signifie moins de hits de cache

• Insertion

C'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 dans un nouveau tableau si le tableau est plein, ce qui rend l'insertion d'un 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 n'importe où sauf à la fin du tableau, dans le cas d'une liste liée, nous n'avons pas besoin de la redimensionner, il vous suffit de mettre à jour les pointeurs.

• Effacement

Cela fonctionne comme des insertions et mieux dans LinkedList que dans un tableau.

Ce sont les implémentations les plus couramment utilisées de Collection.

Liste des tableaux:

• 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)

Vecteur: ne l'utilisez pas. Il s'agit d'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é en O (1)

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

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

En réalité, la localité mémoire a une énorme influence sur les performances du traitement réel.

L'utilisation accrue du streaming de disque dans le traitement «Big Data» par rapport à l'accès aléatoire montre à quel point la structuration de votre application autour de cela peut considérablement améliorer les performances à plus grande échelle.

S'il existe un moyen d'accéder séquentiellement à un tableau, celui-ci est de loin le plus performant. La conception avec ceci comme objectif devrait être au moins considérée si la performance est importante.

Hmm, Arraylist peut être utilisé dans des cas comme suit, je suppose:

1. vous ne savez pas combien d'éléments seront 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)

Utilisez la liste chaînée pour le tri 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 y a une exigence d'ajout et de suppression fréquents dans l'application, LinkedList est le meilleur choix.

2) Les opérations de recherche (méthode d'obtention) sont rapides dans Arraylist (O (1)) mais pas dans LinkedList (O (n)) donc s'il y a moins d'opérations d'ajout et de suppression et plus d'exigences d'opérations de recherche, ArrayList serait votre meilleur pari.

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 indices des éléments du tableau devront être décalés.

Avec une liste chaînée, c'est o (1) car il vous suffit de créer le nœud, de réaffecter la tête et d'assigner la référence à next comme tête précédente.

Lors de l'insertion ou de la suppression fréquente à la fin de la liste, les tableaux sont préférables car la complexité sera o (1), aucune réindexation n'est requise, mais pour une liste chaînée, ce sera o (n) car vous devez partir de la tête au dernier nœud.

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

J'ai fait quelques analyses comparatives et j'ai trouvé 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(string[] args)
        {
            int count = 20000;
            Random rand = new Random(12345);

            Stopwatch watch = Stopwatch.StartNew();
            LinkedList<int> ll = new LinkedList<int>();
            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<int> list = new List<int>();
            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();
        }
    }
}

Cela prend 900 ms pour la liste chaînée et 100 ms pour la classe de liste.

Il crée des listes de nombres entiers ultérieurs. 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 simple tableau.

Les tableaux, de loin, sont les structures de données les plus utilisées. Cependant, les listes chaînées se révèlent utiles à leur manière, lorsque les tableaux sont maladroits - ou chers, pour dire le moins.

Les listes liées sont utiles pour implémenter des piles et des files d'attente dans des situations où leur taille est susceptible de varier. Chaque nœud de la liste liée peut être poussé ou sauté sans déranger la majorité des nœuds. Il en va de même pour l'insertion / suppression de nœuds quelque part au milieu. Dans les tableaux, cependant, tous les éléments doivent être décalés, ce qui est un travail coûteux en termes de temps d'exécution.

Les arbres binaires et les arbres de recherche binaires, les tables de hachage et les essais sont quelques-unes des structures de données dans lesquelles - au moins en C - vous avez besoin de listes chaînées comme ingrédient fondamental pour les construire.

Cependant, les listes chaînées doivent être évitées dans les situations où l'on s'attend à ce qu'il puisse appeler n'importe quel élément arbitraire par son index.

Une réponse simple à la question peut être donnée en utilisant ces points:

1. Les tableaux doivent être utilisés lorsqu'une collection d'éléments de données de type similaire est requise. Alors que la liste liée est une collection d'éléments liés aux données de type mixte appelés nœuds.

2. En tableau, on peut visiter n'importe quel élément en temps O (1). Alors que, dans la liste chaînée, nous aurions besoin de parcourir toute la liste chaînée de la tête au nœud requis en prenant le temps O (n).

3. Pour les tableaux, une taille spécifique doit être déclarée initialement. Mais les listes chaînées sont de taille dynamique.