Pourquoi les listes chaînées plus vite que les tableaux?

Je suis très perplexe à ce sujet. Partout où il y a écrit "les listes chaînées sont plus rapides que les tableaux", mais personne ne prend la peine de dire POURQUOI. À l'aide de la plaine de la logique, je ne comprends pas comment une liste chaînée peut être plus rapide. Dans un tableau toutes les cellules sont à côté les uns des autres tant et aussi longtemps que vous connaissez la taille de chaque cellule, il est facile d'atteindre une cellule instantanément. Par exemple, si il y a une liste de 10 entiers et je veux obtenir la valeur dans la quatrième cellule puis-je aller directement au début de la matrice de+de 24 octets, et lire de 8 octets à partir de là.

Dans l'autre main quand vous avez une liste, et vous souhaitez obtenir l'élément à la quatrième place, alors vous devez commencer à partir du début ou de la fin de la liste(selon si c'est un simple ou un double de la liste) et aller d'un nœud à l'autre jusqu'à ce que vous trouver ce que vous cherchez.

Alors, comment diable pouvez aller étape par étape, être plus rapide que d'aller directement à un élément?

Cela dépend de ce que vous essayez d'accomplir. Si vous voulez la recherche ou de l'accès à un élément spécifique, les tableaux sont plus rapides, mais si vous voulez insérer ou de supprimer un élément, une liste chaînée est plus rapide.
J'aimerais beaucoup voir un lien de quelque part qui fait de cette revendication.
Comme certains ont répondu, rapide est pertinent. Donc, à certains endroits, il est écrit que les tableaux sont plus rapides que les listes chaînées et dans certains endroits, il est écrit que les listes chaînées sont plus rapides que les tableaux. J'ai googlé et n'ai pas trouvé les résultats sur cela et c'est la raison pour laquelle j'ai posté la question ici car j'ai été intrigué. Maintenant avec ma question garni de quelqu'un d'autre qui s'interroge sur la même volonté d'obtenir leur esprit droit.
Ce sujet en.wikipedia.org/wiki/... ?
en tant que débutant, je préfère une plus compliqué de répondre que la lecture de l'ensemble de la wikipedeia et ne pas comprendre quoi que ce soit. Pas tout le monde est à l'aise avec le format de la langue après tout.

OriginalL'auteur Pithikos | 2011-03-26

  1. 13

    Cette question, le titre est trompeur.

    Il affirme que les listes liées sont plus vite que les tableaux sans limiter la portée. Il y a un certain nombre de fois que les tableaux peuvent être significativement plus rapide et il y a un certain nombre de fois une liste, peut être significativement plus rapide: le cas particulier des listes liées "plus rapide" ne semble pas être pris en charge.

    Il y a deux choses à considérer:

    1. Les limites théoriques de listes liées vs tableaux dans une opération particulière; et
    2. le monde réel de la mise en œuvre et l'utilisation du modèle, y compris les cache-localité et des allocations.

    Autant que l'accès à un élément indexé: Le opération est O(1) dans un tableau et comme l'a souligné, est très rapide (juste un décalage). Le opération est O(k) dans une liste liée (où k est l'indice et peut toujours être << n, selon le cas), mais si la liste chaînée est déjà parcouru puis c'est O(1) par étape, qui est "le même" comme un tableau. Si un tableau traversée (for(i=0;i<len;i++) est plus rapide (ou plus lent) dépend notamment de la mise en œuvre de la langue//run-temps.

    Cependant, si il y a un spécifiques cas où le tableau n'est pas plus rapide pour l'une des opérations ci-dessus (chercher ou transversal), il serait intéressant de voir à être disséqué plus en détail. (Je suis sûr qu'il est possible de trouver une langue avec une très dégénérée de la mise en œuvre de tableaux sur les listes toux Haskell toux)

    Heureux de codage.

    Mon simple d'utilisation résumé: les Tableaux sont bons pour l'accès indexé et des opérations qui impliquent la permutation des éléments. Le non-amorti re-taille de l'opération et extra mou (si nécessaire), en revanche, peuvent être assez coûteux. Les listes liées amortir le re-dimensionnement (et du commerce de mou pour un "pointeur" par cellule) et peuvent souvent excel à des opérations comme "les découper ou de l'insertion d'un tas d'éléments." Dans la fin, ils sont différents des données-structures et doit être traitée comme telle.

    OriginalL'auteur

  2. 7

    Comme la plupart des problèmes dans la programmation, le contexte est tout. Vous avez besoin de réfléchir sur les modèles d'accès de vos données, puis de la conception de votre système de stockage de manière appropriée. Si vous insérez quelque chose une seule fois, et ensuite accéder à 1 000 000 de fois, alors, qui se soucie de ce que l'insert coût est? D'autre part, si vous insérer/supprimer aussi souvent que vous le lire, alors que ces coûts en voiture de la décision.

    OriginalL'auteur Peter Rowell

  3. 4

    Dépend de l'opération pour laquelle vous faites allusion. L'ajout ou la suppression d'éléments est beaucoup plus rapide dans une liste, que dans un tableau.

    Itération de manière séquentielle sur la liste un par un est plus ou moins la même vitesse dans une liste, et un tableau.

    D'obtenir un élément spécifique dans le milieu est beaucoup plus rapide dans un tableau.

    Et le tableau pourrait gaspiller de l'espace, parce que très souvent lors de l'expansion de la matrice, plus les éléments sont allouées que de besoin à ce point dans le temps (pensez à liste de tableaux en Java).

    Donc, vous devez choisir votre structure de données en fonction de ce que vous voulez faire:

    beaucoup d'insertions et d'itération séquentielle --> utiliser une LinkedList

    d'accès aléatoire et, idéalement, une taille prédéfinie --> utiliser un tableau

    En référence à l'itération séquentielle, il se peut qu'une liste liée légèrement bord sur les tableaux. Votre affirmation que l'itération de manière séquentielle sur la liste est plus ou moins la même vitesse est probablement correct, mais peut être difficile à mesurer sur les ordinateurs modernes. Je crois que, dans la plus pure contexte, les listes liées bord de tableaux sur itération de la vitesse, comme se déplacer vers le prochain nœud n'a pas besoin de calculer l'adresse de la prochaine offset de mémoire, c'est comme avec les tableaux, car la liste contient l'adresse du nœud suivant.

    OriginalL'auteur a_horse_with_no_name

  4. 3

    Parce qu'aucune mémoire ne soit déplacé lors de l'insertion est faite dans le milieu du tableau.
    Pour le cas de la présentation, de son vrai - les tableaux sont plus rapide, vous avez besoin d'arithmétique seulement pour passer d'un élément à l'autre. Liste liée besoin d'indirection et des fragments de mémoire.
    La clé est de savoir quelle structure utiliser et quand.

    Intéressant de noter que l'INSERTION est plus rapide (comme la suppression), mais pas l'accès indexé, qui a été Pithikos " source de confusion.
    Donc vous voulez dire dans le cas où il y est une gamme complète et que vous voulez ajouter un nouvel élément? Ensuite, assurez-vous d'avoir à redimensionner le tableau entier. Mais que faire si le tableau est vide?
    pour les simples accès, rien ne vaut les tableaux. La question est "Pourquoi les listes chaînées plus vite que les tableaux?" et la réponse de répondre à cette question. Dans la vie réelle demande que vous faites de nombreuses opérations sur le tableau (pensez tri des cas), et c'est la raison pour laquelle sont utilisés plus souvent que les tableaux;
    l'insertion d'un élément dans une seule liste -> juste un alocation . l'insertion d'un élément dans un std:vecteur (tableau) realloc de la mémoire et de déplacer tous les éléments -> le Temps n'est pas constant. Peut être plus grande ou plus petite.

    OriginalL'auteur cprogrammer

  5. 2

    Les listes chaînées sont préférables au fil des tableaux lorsque:

    a) vous avez besoin de constante de temps insertions/délétions de la liste (comme dans l'informatique en temps réel où le temps de prévisibilité est absolument essentiel)

    b) vous ne savez pas comment le nombre d'éléments dans la liste. Avec les tableaux, vous pouvez avoir besoin de re-déclarer et copie de la mémoire si le tableau devient trop gros

    c) vous n'avez pas besoin d'un accès aléatoire à l'un des éléments

    d) vous voulez être en mesure d'insérer des éléments dans le milieu de la liste (comme une file d'attente de priorité)

    Tableaux sont préférables lorsque:

    a) vous avez besoin indexé/aléatoire l'accès aux éléments

    b) vous connaissez le nombre d'éléments dans le tableau à l'avance de sorte que vous pouvez allouer le montant exact de la mémoire pour le tableau

    c) vous avez besoin de vitesse lors d'une itération à travers tous les éléments dans la séquence. Vous pouvez utiliser le pointeur de calcul sur le tableau pour accéder à chaque élément, alors vous avez besoin de rechercher le nœud en fonction du pointeur pour chaque élément dans la liste liée, ce qui peut entraîner des erreurs de page qui peut entraîner une dégradation de leurs performances.

    d) la mémoire est un sujet de préoccupation. Remplis les tableaux de prendre moins de mémoire que les listes chaînées. Chaque élément du tableau est juste les données. Chaque liste liée nœud a besoin de données ainsi qu'une (ou plusieurs) des pointeurs vers d'autres éléments dans la liste chaînée.

    Tableau liste (comme ceux dans .Net vous donner les avantages de tableaux, mais d'allouer dynamiquement des ressources pour vous afin que vous n'avez pas besoin de trop s'inquiéter de la taille de la liste et vous pouvez supprimer des éléments à n'importe quel indice, sans aucun effort ou re-brassage des éléments qui nous entourent. Performance sage, arraylists sont plus lents que les premières tableaux.

    De référence:
    Lamar répondre
    https://stackoverflow.com/a/393578/6249148

    OriginalL'auteur Ahmed Karim