Tableau versus liste liée

une autre bonne raison est que les listes liées se prêtent bien à des implémentations multi-threadées efficaces. La raison en est que les changements ont tendance à être locaux - affectant seulement un ou deux pointeurs pour insérer et supprimer à une partie localisée de la structure de données. Ainsi, vous pouvez avoir beaucoup de threads travaillant sur la même liste liée. De plus, il est possible de créer des versions sans serrure en utilisant des opérations de type CAS et d'éviter les serrures lourdes.

avec un liste liée, les itérateurs peuvent également parcourir la liste pendant que des modifications se produisent. Dans le cas optimiste où les modifications ne s'entrechoquent pas, les itérateurs peuvent continuer sans problème.

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

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

les listes liées ont plusieurs avantages au fil des tableaux. Les éléments peuvent être insérés dans les listes liées indéfiniment, tandis que un tableau va éventuellement soit remplir ou doivent être redimensionnées, cher opération qui peut ne pas être possible si la mémoire est fragmentée. De même, un tableau à partir duquel plusieurs les éléments sont supprimés peuvent devenir inutilement vide ou besoin d'être fait les plus petits.

d'un autre côté, les matrices permettent accès, alors que les listes liées ne permettent que l'accès séquentiel aux éléments. En fait, les listes liées par un seul lien ne peuvent être parcouru dans un sens. Ce fait des listes liées impropres à applications où il est utile de regarder en place d'un élément par son indice rapidement, comme heapsort. L'accès séquentiel sur tableaux est également plus rapide que sur liés listes sur de nombreuses machines en raison de la localité de référence et des caches de données. Lier les listes ne bénéficient pratiquement d'aucun avantage cache.

un autre inconvénient des listes liées est le stockage supplémentaire nécessaire pour les références, ce qui les rend souvent peu pratique pour les listes de petites données des éléments tels que des caractères ou des booléens valeur. Il peut aussi être lent, et avec un naïf allocateur, le gaspillage, à allouer la mémoire séparément pour chaque élément nouveau, un problème général résolu en utilisant des pools de mémoire.

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

j'en ajouterai une autre - les listes peuvent agir comme structures de données" purement fonctionnelles .

par exemple, vous pouvez avoir des listes complètement différentes partageant la même section de fin

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 devoir copier les données pointées par a dans b et c .

C'est pourquoi ils sont si populaires fonctionnelle les langages, qui utilisent des variables immuables - prepend et tail opérations peuvent se produire librement sans avoir à copier les données originales-caractéristiques très importantes lorsque vous traitez les données comme immuables.

fusionner deux listes liées (en particulier deux listes doublement Liées) est beaucoup plus rapide que fusionner deux tableaux (en supposant que la fusion est destructive). Le premier prend O(1), le second prend O (n).

EDIT: pour clarifier, je voulais dire" Fusion " ici dans le sens non ordonné, pas comme dans la sorte de fusion. Peut-être "concaténation" aurait été un meilleur mot.

en plus de l'insertion au milieu de la liste étant plus facile - il est aussi beaucoup plus facile de supprimer du milieu d'une liste liée qu'un tableau.

mais franchement, je n'ai jamais utilisé de liste liée. Chaque fois que j'ai eu besoin d'insertion et de suppression rapides, j'ai aussi eu besoin de recherche rapide, donc je suis allé à un HashSet ou un dictionnaire.

tout d'abord, en C++, les listes liées ne devraient pas être beaucoup plus difficiles à utiliser qu'un tableau. Vous pouvez utiliser le std:: list ou le boost pointer list pour les listes liées. Les problèmes clés avec les listes liées vs tableaux sont l'espace supplémentaire requis pour les pointeurs et accès aléatoire terrible. Vous devez utiliser une liste liée si vous

• vous n'avez pas besoin d'un accès aléatoire aux données
• , vous serez Ajout / Suppression d'éléments, en particulier au milieu de la liste

un argument largement non apprécié pour ArrayList et contre LinkedList est que les LinkedLists sont inconfortables pendant le débogage . Le temps passé par les développeurs de maintenance à comprendre le programme, par exemple pour trouver des bogues, augmente et IMHO ne justifie parfois pas les nanosecondes dans les améliorations de performance ou les octets dans la consommation de mémoire dans les applications d'entreprise. Parfois (bien sûr cela dépend du type d'applications), il est préférable de perdre quelques octets, mais avoir une application qui est plus facile à maintenir ou plus facile à comprendre.

par exemple, dans un environnement Java et en utilisant le débogueur Eclipse, déboguer un ArrayList révélera une structure très facile à comprendre:

arrayList   ArrayList<String>
  elementData   Object[]
    [0] Object  "Foo"
    [1] Object  "Foo"
    [2] Object  "Foo"
    [3] Object  "Foo"
    [4] Object  "Foo"
    ...

d'un autre côté, regarder le contenu d'une liste de liens et trouver des objets spécifiques devient un cauchemar de clic D'extension de L'arbre, sans parler de la tête de ligne cognitive nécessaire pour filtrer la liste de liens internes:

linkedList  LinkedList<String>
    header  LinkedList$Entry<E>
        element E
        next    LinkedList$Entry<E>
            element E   "Foo"
            next    LinkedList$Entry<E>
                element E   "Foo"
                next    LinkedList$Entry<E>
                    element E   "Foo"
                    next    LinkedList$Entry<E>
                    previous    LinkedList$Entry<E>
                    ...
                previous    LinkedList$Entry<E>
            previous    LinkedList$Entry<E>
        previous    LinkedList$Entry<E>

Pour moi, c'est comme ça", 151910920"

1. accès

   • Listes autoriser uniquement l'accès séquentiel aux éléments. Ainsi, la complexité algorithmique est de l'ordre de O(n)
   • les matrices permettent un accès aléatoire à ses éléments et donc la complexité est de l'ordre de O(1)

2. stockage

   • listes nécessitent un stockage supplémentaire pour les références. Cela les rend impraticables pour les listes de petits éléments de données tels que les caractères ou les valeurs booléennes.
   • matrices n'ont pas besoin d'un stockage supplémentaire pour pointer vers l'élément de données suivant. Chaque élément est accessible via des index.

3. Taille

   • la taille de les listes liées sont par nature dynamiques.
   • la taille de array est limitée à la déclaration.

4. Insertion / Suppression

   • des éléments peuvent être insérés et supprimés dans listes liées indéfiniment.
   • Insertion / Suppression de valeurs dans les tableaux sont très coûteux. Cela nécessite une réallocation de la mémoire.

deux choses:

coder une liste liée est, sans doute, un peu plus de travail que d'utiliser un tableau et il s'est demandé ce qui justifierait l'effort supplémentaire.

ne code jamais une liste liée en utilisant C++. Suffit d'utiliser la STL. La difficulté de la mise en œuvre ne devrait jamais être une raison pour choisir une structure de données plutôt qu'une autre, car la plupart sont déjà mises en œuvre là-bas.

comme pour les différences réelles entre un tableau et une liste liée, la grande chose pour moi est comment vous prévoyez d'utiliser la structure. Je vais utiliser le terme de vecteur puisque c'est le terme pour un tableau redimensionnable en C++.

indexer dans une liste liée est lent parce que vous devez parcourir la liste pour obtenir l'index donné, alors qu'un vecteur est contigu dans la mémoire et vous pouvez y arriver en utilisant pointer math.

ajouter à la fin ou au début d'une liste liée est facile, puisque vous n'avez qu'à mettre à jour un lien, où dans un vecteur vous pouvez avoir à redimensionner et copier le contenu plus.

enlever un élément d'une liste est facile, puisque vous avez juste à briser une paire de liens et puis les attacher à nouveau ensemble. Supprimer un élément d'un vecteur peut être plus rapide ou plus lent, selon que vous vous souciez de l'ordre. L'échange dans le dernier article au-dessus de l'article que vous voulez enlever est plus rapide, tandis que le déplacement de tout après lui vers le bas est plus lent, mais conserve la commande.

Eric Lippert a récemment eu un post sur l'une des raisons pour lesquelles les tableaux devraient être utilisés de façon conservatrice.

l'insertion et la suppression rapides sont en effet les meilleurs arguments pour les listes liées. Si votre structure se développe dynamiquement et que l'accès en temps constant à n'importe quel élément n'est pas nécessaire (comme les piles et les files d'attente dynamiques), les listes liées sont un bon choix.

En voici un rapide: L'enlèvement des articles est plus rapide.

Linked-list sont particulièrement utiles lorsque la collection est en constante croissance et rétrécit. Par exemple, il est difficile d'imaginer essayer d'implémenter une file d'attente (ajouter à la fin, Supprimer de l'avant) en utilisant un tableau -- vous passeriez tout votre temps à déplacer les choses vers le bas. D'autre part, il est trivial avec une liste liée.

mis à part ajouter et supprimer du milieu de la liste, j'aime les listes liées plus parce qu'elles peuvent croître et se rétrécir dynamiquement.

plus personne ne Code sa propre liste de liens. Ce serait idiot. La prémisse que l'utilisation d'une liste liée prend plus de code est tout simplement faux.

de nos jours, l'établissement d'une liste de liens n'est qu'un exercice pour les élèves afin qu'ils puissent comprendre le concept. Au lieu de cela, tout le monde utilise une liste pré-construite. En C++, basé sur la description de notre question, cela signifierait probablement un vecteur stl ( #include <vector> ).

par conséquent, le choix d'une liste liée vs un array est entièrement sur la pesée des différentes caractéristiques de chaque structure par rapport aux besoins de votre application. Surmonter la programmation supplémentaire fardeau devrait être sans incidence sur la décision.

c'est en fait une question d'efficacité, le fait d'insérer, de supprimer ou de déplacer (là où vous n'êtes pas simplement en train d'échanger) des éléments à l'intérieur d'une liste liée est minime, c'est-à-dire que l'opération elle-même est O(1), versets O(n) pour un tableau. Cela peut faire une différence significative si vous travaillez lourdement sur une liste de données. Vous choisissez vos types de données en fonction de la façon dont vous allez les utiliser et choisissez le plus efficace pour l'algorithme que vous utilisez.

ont un sens là où le nombre exact d'articles sera connu, et où la recherche par index a un sens. Par exemple, si je voulais stocker l'état exact de ma sortie vidéo à un moment donné sans compression, j'utiliserais probablement un tableau de taille [1024][768]. Cela va me donner exactement ce dont j'ai besoin, et la liste serait beaucoup, beaucoup plus lent pour obtenir la valeur d'un pixel donné. Dans les endroits où un tableau n'a pas de sens, il y a généralement de meilleurs types de données qu'une liste pour traiter efficacement les données.

Tableaux Vs Liste Liée:

1. L'allocation de mémoire de tableau va échouer parfois en raison de la mémoire fragmentée.
La mise en cache
2. est préférable dans les tableaux car tous les éléments sont alloués espace mémoire contigu.
Le codage de
3. est plus complexe que celui des tableaux.
4. aucune contrainte de taille sur la liste liée, contrairement aux tableaux
5. L'Insertion/Suppression est plus rapide dans la liste liée et l'accès est plus rapide dans les tableaux.
6. liste mieux liée du point de vue multi-threading.

comme les tableaux sont de nature statique, donc toutes les opérations comme l'allocation de mémoire se produisent au moment de la compilation seulement. Le processeur doit donc faire moins d'efforts à son exécution .

supposons que vous ayez un ensemble ordonné, que vous voulez aussi modifier en ajoutant et en supprimant des éléments. En outre, vous avez besoin de la capacité de conserver une référence à un élément de telle manière que plus tard, vous pouvez obtenir un élément précédent ou suivant. Par exemple, une liste ou d'un ensemble de paragraphes dans un livre.

tout d'abord, nous devrions noter que si vous voulez conserver des références à des objets en dehors de l'ensemble lui-même, vous finirez probablement par stocker des pointeurs dans le tableau, plutôt que de stocker les objets eux-mêmes. Sinon, vous ne pourrez pas insérer dans le tableau - si les objets sont intégrés dans le tableau, ils se déplaceront pendant les insertions et tout pointeur vers eux deviendra invalide. En est de même pour les indices de tableau.

votre premier problème, comme vous l'avez vous - même noté, est la liste liée à l'insertion qui permet L'insertion dans O(1), mais un tableau nécessite généralement O(n). Ce problème peut être partiellement contourné, il est possible de créer une structure de données qui donne l'interface d'accès par réseau, telle une matrice, où la lecture et l'écriture sont, au pire, logarithmique.

votre deuxième problème, et plus grave est que, compte tenu d'un élément trouver l'élément suivant est O(n). Si l'ensemble n'a pas été modifié vous pouvez conserver l'index de l'élément comme référence au lieu du pointeur faisant ainsi find-next une opération O(1), mais comme c'est tout ce que vous avez est un pointeur vers l'objet lui-même et aucun moyen de déterminer son index actuel dans le tableau autrement que par balayage du "tableau" entier. C'est un problème insurmontable pour les tableaux - même si vous pouvez optimiser les insertions, il n'y a rien que vous pouvez faire pour optimiser l'opération de type find-next.

dans un tableau vous avez le privilège d'accéder à n'importe quel élément dans le temps O(1). Donc, il est adapté pour les opérations comme la recherche binaire tri rapide, etc Liste liée d'autre part est adapté à l'insertion Suppression que son en O(1) Temps. Les deux a des avantages aussi bien que des inconvénients et de préférer l'un par rapport à l'autre se résume à ce que vous voulez mettre en œuvre.

-- la grande question Est de savoir si nous pouvons avoir un hybride des deux. Quelque chose comme ce que python et perl implémentent sous forme de listes.

Liste

son plus préférable quand il s'agit de l'insertion! Fondamentalement, ce qui est n'est qu'il traite avec le pointeur

1 -> 3 -> 4

Insérer (2)

1........3......4

.....2

enfin

1 -> 2 -> 3 -> 4

une flèche à partir des 2 points à 3 et la flèche de 1 points à 2

de Simples!

Mais à partir de la Matrice de

| 1 | 3 | 4 |

Insérer (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |

n'importe qui peut visualiser la différence! Juste pour 4 index nous effectuons 3 étapes

et si la longueur du réseau est d'un million alors? Est la matrice de efficace? La réponse est non! :)

la même chose vaut pour la suppression! Dans Nous pouvons simplement utiliser le pointeur et annuler l'élément et le suivant dans la classe objet! Mais pour array, nous devons effectuer shiftLeft ()

Espère que ça aide! :)

liste liée sont plus d'un overhead à maintenir que le tableau, il nécessite également un stockage mémoire supplémentaire tous ces points sont convenus. Mais il y a quelques choses que le tableau ne peut pas faire. Dans de nombreux cas supposez que vous voulez un tableau de longueur 10^9 Vous ne pouvez pas l'obtenir parce que l'obtention d'un emplacement de mémoire continue doit être là. Liste liée pourrait être un sauveur ici.

supposons que vous voulez stocker plusieurs choses avec des données alors elles peuvent être facilement étendues dans la liste liée.

ont généralement une implémentation de liste liée en arrière-plan.

différence entre ArrayList et LinkedList

ArrayList et LinkedList à la fois la mise en œuvre des List interface et maintient l'ordre d'insertion. Les deux sont des classes non synchronisées. Mais il y a beaucoup de différences entre les classes ArrayList et LinkedList qui sont données ci-dessous.

liste de tableaux -

1. ArrayList utilise en interne tableau dynamique pour stocker les éléments .

2. la Manipulation avec ArrayList est lente parce qu'elle utilise à l'interne array. Si un élément est retiré du tableau, tous les bits sont déplacés mémoire.

3. ArrayList classe d'agir comme une liste seulement parce qu'il met en œuvre List seulement.
4. ArrayList est mieux pour stocker et accéder données.

LinkedList -

1. LinkedList utilise à l'interne liste doublement liée pour stocker les éléments .

2. Manipulation avec LinkedList est plus rapide que ArrayList parce qu'il utilise la liste doublement liée de sorte qu'aucun changement de bit n'est nécessaire dans la mémoire.

3. La classe LinkedList peut agir comme une liste et une file d'attente à la fois parce qu'elle implémente les interfaces List et "Deque".

4. LinkedList est préférable pour manipuler des données.

seule raison d'utiliser la liste liée est que l'insertion de l'élément est facile (suppression également).

L'inconvénient pourrait être que les pointeurs prennent beaucoup d'espace.

et à propos de ce codage est plus difficile: Habituellement, vous n'avez pas besoin de liste de codes liés (ou seulement une fois) ils sont inclus dans STL et il n'est pas si compliqué si vous avez encore à faire.

je pense aussi que la liste de liens est mieux que les tableaux. parce que nous traversons dans la liste de liens mais pas dans les tableaux

selon votre langue, certains de ces inconvénients et avantages pourraient être considérés:

C Langage de programmation : lors de l'utilisation d'une liste liée (par le biais de pointeurs de struct typiquement), une attention particulière doit être faite pour s'assurer que vous n'êtes pas une fuite de mémoire. Comme il a été mentionné précédemment, les listes liées sont faciles à mélanger, parce que tout ce que l'on fait, c'est changer les pointeurs, mais est-ce qu'on va se rappeler de tout libérer?

Java : Java a une collecte automatique des déchets, donc la fuite de la mémoire ne sera pas un problème, mais caché du programmeur de haut niveau est les détails d'implémentation de ce qu'est une liste liée. Des méthodes telles que la suppression d'un nœud à partir du milieu de la liste est plus compliqué d'une procédure que certains utilisateurs de la langue attendre d'elle.

pourquoi une liste liée sur un tableau ? Comme certains l'ont déjà dit, plus grande vitesse des insertions et des suppressions.

mais peut-être que nous n'avons pas à vivre avec les limites de l'un ou l'autre, et obtenir le meilleur des deux, en même temps... hein???

pour les suppressions de tableau, vous pouvez utiliser un byte 'Deleted', pour représenter le fait qu'une ligne a été supprimée, ainsi le réarrangement du tableau n'est plus nécessaire. Pour alléger le fardeau des insertions, ou de données, l'utilisation d'une liste liée. Ensuite, lorsque vous vous y référez, faites d'abord votre recherche logique l'une, puis l'autre. Ainsi, en utilisant en combinaison vous donne le meilleur des deux.

si vous avez un tableau vraiment grand, vous pouvez le combiner avec un autre, tableau beaucoup plus petit ou la liste liée où le plus petit tient thes 20, 50, 100 articles les plus récemment utilisés. Si le nécessaire n'est pas dans la courte liste ou d'une matrice, vous allez sur le grand tableau. Si trouvé là, vous pouvez alors ajoutez-le à la liste/tableau lié plus petit sur la présomption que "les choses les plus récemment utilisées sont les plus susceptibles d'être réutilisées" (et oui, peut-être en remplaçant l'article Le moins récemment utilisé de la liste ). Ce qui est vrai dans de nombreux cas et a résolu un problème que j'ai dû aborder dans un .Module de vérification des autorisations de sécurité ASP, avec facilité, élégance et vitesse impressionnante.

alors que beaucoup d'entre vous ont abordé les adv./dis de la liste liée vs tableau, la plupart des comparaisons sont comment l'un est meilleur/ pire que l'autre.Eg. vous pouvez faire l'accès aléatoire dans le tableau mais pas possible dans la liste liée et d'autres. Cependant, ceci suppose que les listes de liens et les tableaux vont être appliqués dans une application similaire. Cependant, une réponse correcte devrait être la façon dont la liste de liens serait préférée au tableau et vice-versa dans un déploiement d'application particulier. Supposons que vous voulez mettre en œuvre une application de dictionnaire, qu'utiliseriez-vous ? Tableau: mmm il permettrait la récupération facile par la recherche binaire et d'autres algo de recherche .. mais réfléchissons à la façon dont la liste de liens peut être mieux..Dis que tu veux chercher "Blob" dans le dictionnaire. Serait-il logique d'avoir une liste de liens A->B->C->D--- - >Z et ensuite chaque élément de liste pointant également vers un tableau ou une autre liste de tous les mots commençant par cette lettre ..

A -> B -> C -> ...Z
|    |    |
|    |    [Cat, Cave]
|    [Banana, Blob]
[Adam, Apple]

est maintenant l'approche ci-dessus mieux ou un tableau plat de [Adam, pomme, banane,Blob, chat, Cave]? Serait-ce possible avec array ? Donc un avantage majeur de la liste de liens est que vous pouvez avoir un élément pointant non seulement vers l'élément suivant mais aussi vers une autre liste de liens/Tableau/ tas/ ou tout autre emplacement de mémoire. Tableau est un plat états contigus en mémoire découpée en blocs de taille de l'élément, il va stocker.. La liste de liens d'autre part est un morceau d'unités de mémoire non contiguës (peut être n'importe quelle taille et peut stocker n'importe quoi) et pointant l'un vers l'autre la voie vous voulez. De même, disons que vous faites un lecteur USB. Voulez-vous maintenant que les fichiers soient sauvegardés sous forme de tableau ou de liste de liens ? Je pense que vous avez l'idée de ce que je suis pointant vers :)