Tableau versus liste liée

200

Pourquoi quelqu'un voudrait-il utiliser une liste chaînée sur un tableau?

Coder une liste chaînée est, sans aucun doute, un peu plus de travail que d'utiliser un tableau et on peut se demander ce qui justifierait l'effort supplémentaire.

Je pense que l'insertion de nouveaux éléments est triviale dans une liste chaînée, mais c'est une corvée majeure dans un tableau. Y a-t-il d'autres avantages à utiliser une liste chaînée pour stocker un ensemble de données par rapport au stockage dans un tableau?

Cette question n'est pas un double de cette question car l'autre question concerne spécifiquement une classe Java particulière alors que cette question concerne les structures de données générales.

Onorio Catenacci
la source
1
Connexes - Quand utiliser LinkedList <> sur ArrayList <>? - c'est Java, mais les tableaux (ArrayList) et les listes liées ont probablement les mêmes performances dans n'importe quel langage.
Bernhard Barker
1
@rootTraveller En fait, cette question serait un double de cette question car ma question a été publiée en premier.
Onorio Catenacci

Réponses:

147
  • Il est plus facile de stocker des données de différentes tailles dans une liste chaînée. Un tableau suppose que chaque élément a exactement la même taille.
  • Comme vous l'avez mentionné, il est plus facile pour une liste chaînée de croître de manière organique. La taille d'une baie doit être connue à l'avance ou recréée lorsqu'elle doit croître.
  • Mélanger une liste chaînée consiste simplement à modifier ce qui pointe vers quoi. Mélanger un tableau est plus compliqué et / ou prend plus de mémoire.
  • Tant que vos itérations se produisent toutes dans un contexte "foreach", vous ne perdez aucune performance dans l'itération.
Ryan
la source
19
Comment les articles de différentes tailles sont-ils traités différemment? Une liste chaînée utilise soit une structure fixe avec un champ suivant (nécessite une taille fixe), soit stocke un pointeur vers les données dans la voiture (taille variable OK). Les deux approches sont tout aussi faciles avec un vecteur. De même pour le brassage.
Brian
32
Je dirais que mélanger un tableau est moins compliqué.
Hugh Allen
23
Cette réponse est incorrecte et trompeuse. (sauf pour avoir besoin de connaître la taille d'un tableau lorsque vous le déclarez)
Robert Paulson
35
L'itération d'une liste chaînée ne serait-elle pas plus lente en raison de la localisation des données?
Firas Assaad
6
@Rick, les vecteurs surutilisent généralement l'espace dont ils ont besoin pour ne pas avoir à allouer de nouvel espace chaque fois que la taille augmente. Le résultat est que les vecteurs sont généralement beaucoup moins gourmands en mémoire, pas plus que les listes liées.
Winston Ewert
179

Une autre bonne raison est que les listes chaînées se prêtent bien à des implémentations multi-thread efficaces. La raison en est que les changements ont tendance à être locaux - n'affectant qu'un ou deux pointeurs à insérer et à supprimer sur une partie localisée de la structure de données. Ainsi, vous pouvez avoir plusieurs threads travaillant sur la même liste chaînée. De plus, il est possible de créer des versions sans verrouillage en utilisant des opérations de type CAS et d'éviter complètement les verrous lourds.

Avec une liste chaînée, les itérateurs peuvent également parcourir la liste pendant les modifications. Dans le cas optimiste où les modifications ne se heurtent pas, les itérateurs peuvent continuer sans contention.

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 se fasse sans verrou global sur l'ensemble du tableau, de sorte que les modifications arrêtent les affaires du monde.

Alex Miller
la source
9
Alex - c'est une considération intéressante qui ne me serait jamais venue à l'esprit. Très bonne réponse. Je vous voterais deux fois si je le pouvais. :-)
Onorio Catenacci
5
Jetez un œil aux listes de sauts (en particulier ConcurrentSkipListMap dans Java 6) pour avoir une bonne idée de la direction à suivre. CSLM est une carte concurrente triée avec d'excellentes performances. Loin, bien mieux qu'un TreeMap synchronisé. tech.puredanger.com/2007/10/03/skip-lists
Alex Miller
... sauf que ConcurrentSkipListMapou ConcurrentSkipListMaplistes ne sont pas, même si « Liste » se produit quelque part dans leur nom. Les deux nécessitent des clés qui seront triées et uniques. Si vous avez besoin d'une Liststructure de données, c'est-à-dire qui permet de dupliquer des éléments dans un ordre arbitraire, cela ne convient pas et vous devrez faire de grands efforts pour créer une structure de données comme LinkedListune chose pouvant être mise à jour simultanément. Si vous n'avez besoin que d'une file d'attente ou d'une suppression simultanée, eh bien oui, il existe même des exemples existants, mais un concurrent List… Je ne suis pas convaincu que cela soit même possible.
Holger
128

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

Les listes liées ont plusieurs avantages par rapport aux tableaux. Les éléments peuvent être insérés indéfiniment dans des listes liées, tandis qu'un tableau finira par se remplir ou devra être redimensionné, une opération coûteuse qui peut même ne pas être possible si la mémoire est fragmentée. De même, un tableau dont de nombreux éléments sont supprimés peut devenir inutilement vide ou doit être réduit.

D'un autre côté, les tableaux permettent un accès aléatoire, tandis que les listes liées n'autorisent qu'un accès séquentiel aux éléments. En fait, les listes à liaison unique ne peuvent être parcourues que dans une seule direction. Cela rend les listes liées inappropriées pour les applications où il est utile de rechercher rapidement un élément par son index, tel que le tri par tas. L'accès séquentiel sur les tableaux est également plus rapide que sur les listes liées sur de nombreuses machines en raison de la localité de référence et des caches de données. Les listes liées ne reçoivent presque aucun avantage du 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 pratiques pour les listes de petits éléments de données tels que les caractères ou les valeurs booléennes. Il peut également être lent, et avec un allocateur naïf, inutile, d'allouer de la mémoire séparément pour chaque nouvel élément, problème généralement résolu en utilisant des pools de mémoire.

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

Jonas Klemming
la source
4
Ceci est la réponse parfaite. Décrit succinctement les avantages et les inconvénients des deux.
Rick
merci)) mort simple mais je ne l'ai pas vu dans wiki)
Timur Fayzrakhmanov
58

J'en ajouterai un autre - les listes peuvent agir comme des 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 avoir à copier les données pointées par adans bet c.

C'est pourquoi ils sont si populaires dans les langages fonctionnels, qui utilisent des variables immuables - prependet les tailopérations peuvent se produire librement sans avoir à copier les données d'origine - des fonctionnalités très importantes lorsque vous traitez les données comme immuables.

Brian
la source
4
Encore une autre considération très intéressante que je n'aurais jamais imaginée. Je vous remercie.
Onorio Catenacci
Comment puis-je faire cela en python?
Surexchange
29

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

Mais franchement, je n'ai jamais utilisé de liste chaînée. Chaque fois que j'avais besoin d'une insertion et d'une suppression rapides, j'avais également besoin d'une recherche rapide, alors je suis allé à un HashSet ou à un dictionnaire.

Tom Ritter
la source
2
Très vrai, l'insertion et la suppression interviennent après la recherche la plupart du temps, il faut donc également considérer la somme des complexités temporelles.
MA Hossain Tonu
28

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

EDIT: Pour clarifier, je voulais dire «fusionner» ici dans le sens non ordonné, pas comme dans le type de fusion. Peut-être que «concaténer» aurait été un meilleur mot.

rampion
la source
2
Seulement si vous ajoutez simplement une liste à l'autre. Si vous fusionnez réellement deux listes triées, il faudra plus de journal que O (1).
Herms
3
@Herms, mais vous pouvez fusionner deux listes liées triées sans allouer de mémoire supplémentaire, en parcourant simplement les deux listes et en définissant les pointeurs de manière appropriée. La fusion de deux tableaux prendrait normalement au moins un tableau supplémentaire.
Paul Tomblin
1
Oui, la fusion des listes est plus efficace en mémoire, mais ce n'était pas vraiment ce que je commentais. Dire que la fusion de listes chaînées est O (1) est très trompeur sans clarification du cas.
Herms
La fusion de listes @Herms n'est pas plus efficace en mémoire que la fusion de tableaux sous n'importe quel modèle de données sensible.
Alexei Averchenko
2
Alexei Averchenko: Concaténer deux listes, ou même fusionner-trier deux listes triées, peut être fait sur place, avec la mémoire O (1). La concaténation de deux tableaux nécessite nécessairement de la mémoire O (n), sauf si les tableaux sont déjà adjacents en mémoire. Je pense que le point que vous visez est celui où une liste de n éléments et un tableau de n éléments prennent tous deux la mémoire O (n), mais le coefficient est plus élevé pour les listes chaînées.
rampion
17

Un argument largement méconnu pour ArrayList et contre LinkedList est que les LinkedLists sont inconfortables lors du débogage . Le temps passé par les développeurs de maintenance pour comprendre le programme, par exemple pour trouver des bogues, augmente et à mon humble avis ne justifie parfois pas les nanosecondes d'amélioration des performances ou les octets de consommation de mémoire dans les applicatons d'entreprise. Parfois (eh bien, cela dépend du type d'applications), il vaut mieux gaspiller quelques octets mais avoir une application plus facile à gérer ou à comprendre.

Par exemple, dans un environnement Java et en utilisant le débogueur Eclipse, le débogage d'une liste de tableaux 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 LinkedList et trouver des objets spécifiques devient un cauchemar en cliquant sur Expand-The-Tree, sans parler de la surcharge cognitive nécessaire pour filtrer les éléments internes de LinkedList:

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>
mhaller
la source
17

Tout d'abord, en C ++, les listes liées ne devraient pas être beaucoup plus difficiles à utiliser qu'un tableau. Vous pouvez utiliser la liste std :: list ou la liste de pointeurs boost pour les listes liées. Les principaux problèmes avec les listes liées par rapport aux tableaux sont l'espace supplémentaire requis pour les pointeurs et un accès aléatoire terrible. Vous devez utiliser une liste chaînée si vous

  • vous n'avez pas besoin d'un accès aléatoire aux données
  • vous ajouterez / supprimerez des éléments, en particulier au milieu de la liste
David Nehme
la source
14

Pour moi, c'est comme ça,

  1. Accès

    • Les listes liées n'autorisent qu'un accès séquentiel aux éléments. Ainsi la complexité algorithmique est de l'ordre de O (n)
    • Les tableaux permettent un accès aléatoire à ses éléments et donc la complexité est de l'ordre de O (1)
  2. Espace de rangement

    • Les listes liées nécessitent un stockage supplémentaire pour les références. Cela les rend peu pratiques pour les listes de petits éléments de données tels que les caractères ou les valeurs booléennes.
    • Les tableaux 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 des listes liées est dynamique par nature.
    • La taille du tableau est limitée à la déclaration.
  4. Insertion / suppression

    • Les éléments peuvent être insérés et supprimés indéfiniment dans les listes liées .
    • L'insertion / suppression de valeurs dans des tableaux coûte très cher. Il nécessite une réallocation de mémoire.
Sulman
la source
Vous avez 2 numéro 2 et 2 numéro 3 :)
Hengameh
Nous pouvons déclarer un tableau vide et continuer à ajouter des données comme requis. Comment cela fait-il encore une taille fixe?
HebleV
11

Deux choses:

Coder une liste chaînée est sans aucun doute un peu plus de travail que d'utiliser un tableau et il s'est demandé ce qui justifierait l'effort supplémentaire.

Ne codez jamais une liste liée lorsque vous utilisez C ++. Utilisez simplement la STL. La difficulté de l'implémentation ne devrait jamais être une raison de choisir une structure de données plutôt qu'une autre, car la plupart sont déjà implémentées.

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

L'indexation dans une liste chaînée est lente car vous devez parcourir la liste pour accéder à l'index donné, tandis qu'un vecteur est contigu en mémoire et vous pouvez y accéder en utilisant le calcul du pointeur.

L'ajout à la fin ou au début d'une liste chaînée est facile, car vous n'avez qu'à mettre à jour un lien, où dans un vecteur vous devrez peut-être redimensionner et copier le contenu.

La suppression d'un élément d'une liste est facile, car il vous suffit de rompre une paire de liens, puis de les rattacher. La suppression d'un article d'un vecteur peut être plus rapide ou plus lente, selon que vous vous souciez de la commande. L'échange du dernier élément par-dessus l'élément que vous souhaitez supprimer est plus rapide, tandis que tout déplacer après est plus lent mais conserve l'ordre.

bradtgmurray
la source
Comme je l'ai dit à quelqu'un ci-dessus, j'essayais simplement de relier la question à la façon dont elle m'a été posée. De toute façon, je n'utiliserais jamais un tableau (ou une liste liée roll-my-own) en C ++ - j'utiliserais les versions STL des deux.
Onorio Catenacci
10

Eric Lippert a récemment publié un article sur l'une des raisons pour lesquelles les tableaux doivent être utilisés avec prudence.

Rik
la source
2
Certes, un bon article, mais pas pertinent dans une liste liée par rapport à la discussion du tableau.
Robert Paulson
2
Je dirais qu'une grande partie de l'article d'Eric est pertinent, car il traite à la fois des inconvénients des tableaux et des avantages des listes, indépendamment de l'implémentation de la liste.
Bevan
8

L'insertion et la suppression rapides sont en effet les meilleurs arguments pour des listes chaînées. Si votre structure se développe de manière dynamique et qu'aucun accès à temps constant à aucun élément n'est requis (comme les piles et les files d'attente dynamiques), les listes liées sont un bon choix.

Firas Assaad
la source
7

En voici un rapide: la suppression d'articles est plus rapide.

itsmatt
la source
7

La liste des liens est particulièrement utile lorsque la collection est en constante augmentation et diminution. Par exemple, il est difficile d'imaginer essayer d'implémenter une file d'attente (ajouter à la fin, supprimer de l'avant) à l'aide d'un tableau - vous passeriez tout votre temps à déplacer les choses vers le bas. D'un autre côté, c'est trivial avec une liste chaînée.

James Curran
la source
4
Vous pourriez avoir une file d'attente basée sur un tableau sans trop de travail qui était encore rapide / efficace. Il vous suffirait de garder une trace de quel index était la "tête" et qui était la "queue". Cela fonctionne assez bien si vous avez besoin d'une file d'attente de taille fixe (par exemple, un tampon clavier dans un noyau).
Herms
3
Et est appelé "tampon circulaire", si vous voulez le rechercher dans votre référence d'algorithme préférée.
Steve Jessop
7

Outre l'ajout et la suppression du milieu de la liste, j'aime davantage les listes liées car elles peuvent croître et se réduire dynamiquement.

Vasil
la source
6
Les vecteurs (= essentiellement des tableaux) peuvent également le faire et leur coût amorti est généralement inférieur à celui des listes en raison de problèmes de localité de référence.
Konrad Rudolph
7

Personne ne code plus sa propre liste de liens. Ce serait idiot. L'hypothèse selon laquelle l'utilisation d'une liste chaînée nécessite plus de code est tout simplement fausse.

De nos jours, la création d'une liste chaînée n'est qu'un exercice pour les étudiants afin qu'ils puissent comprendre le concept. Au lieu de cela, tout le monde utilise une liste prédéfinie. 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 chaînée par rapport à un tableau consiste entièrement à peser les différentes caractéristiques de chaque structure par rapport aux besoins de votre application. Surmonter la charge de programmation supplémentaire ne devrait avoir aucun impact sur la décision.

Joel Coehoorn
la source
2
Er..umm .. Le std :: vector est un tableau, pas une liste chaînée. La liste chaînée standard est, eh bien, std :: list.
James Curran
1
oui, mais je pense que le vecteur est plus proche de ce que l'op demande - un remplacement de tableau dynamique.
Joel Coehoorn
@ Joel, j'essayais juste de relier la question telle qu'elle m'a été posée par cet homme qui essaie d'apprendre le C ++. Je ne prendrais pas la peine de coder ma propre liste de liens non plus, mais c'est ainsi qu'il m'a demandé. :-)
Onorio Catenacci
Dans les environnements à mémoire limitée (microcontrôleurs) pour lesquels il existe des compilateurs personnalisés, tout le langage (par exemple, les conteneurs en C ++) n'est pas implémenté. Il se peut donc que vous deviez coder votre propre liste de liens. nongnu.org/avr-libc/user-manual/FAQ.html#faq_cplusplus
Minh Tran
6

C'est vraiment une question d'efficacité, la surcharge pour insérer, supprimer ou déplacer (où vous n'échangez pas simplement) des éléments dans une liste chaînée est minime, c'est-à-dire que l'opération elle-même est O (1), vers O (n) pour un tableau. Cela peut faire une différence significative si vous travaillez fortement sur une liste de données. Vous avez choisi 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.

Steve Baker
la source
6

Les tableaux ont un sens là où le nombre exact d'éléments sera connu et où la recherche par index est logique. 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 me fournira exactement ce dont j'ai besoin, et une liste serait beaucoup, beaucoup plus lente pour obtenir la valeur d'un pixel donné. Dans les endroits où un tableau n'a pas de sens, il existe généralement de meilleurs types de données qu'une liste pour traiter efficacement les données.

tloach
la source
6

Arrays Vs Linked List:

  1. L'allocation de mémoire de la baie échoue parfois en raison d'une mémoire fragmentée.
  2. La mise en cache est meilleure dans les tableaux car tous les éléments se voient allouer de l'espace mémoire contigu.
  3. Le codage est plus complexe que les 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 liée mieux du point de vue multi-threading.
AKS
la source
-1: Tous ces éléments doivent être justifiés, pas seulement énumérés.
John Saunders
Chaque point a déjà été expliqué dans les réponses ci-dessus. Étant retardataire, je n'avais pas d'autre choix que d'énumérer. BTW, lequel aimeriez-vous qu'on vous explique?
AKS
S'ils ont déjà été expliqués, alors pourquoi répondez-vous?
John Saunders
2
Pour qu'il vous donne un aperçu de la discussion. Et j'aime ce genre de réponses pour ne pas avoir à lire la même explication encore et encore. Et je l'ai fait pour ces gens qui ont le même style de pensée que le mien. Différents ppl ont des styles différents. Rien de nouveau.
AKS
3

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

debayan
la source
3

Supposons que vous ayez un ensemble ordonné, que vous souhaitez également modifier en ajoutant et en supprimant des éléments. De plus, vous devez pouvoir conserver une référence à un élément de telle manière que vous puissiez ultérieurement obtenir un élément précédent ou suivant. Par exemple, une liste de tâches ou un ensemble de paragraphes dans un livre.

Tout d'abord, nous devons noter que si vous souhaitez 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 des objets eux-mêmes. Sinon, vous ne pourrez pas insérer dans le tableau - si des objets sont intégrés dans le tableau, ils se déplaceront pendant les insertions et tous les pointeurs vers eux deviendront invalides. Il en va de même pour les index de tableau.

Votre premier problème, comme vous l'avez remarqué vous-même, est que la liste liée par insertion permet l'insertion dans O (1), mais un tableau nécessite généralement O (n). Ce problème peut être partiellement résolu - il est possible de créer une structure de données qui donne une interface d'accès ordonnée de type tableau où la lecture et l'écriture sont, au pire, logarithmiques.

Votre deuxième problème, plus grave, est qu'étant donné 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, ce qui fait de find-next une opération O (1), mais comme il ne vous reste qu'un pointeur vers l'objet lui-même et aucun moyen pour déterminer son index actuel dans le tableau autrement qu'en scannant l'ensemble du "tableau". Il s'agit d'un problème insurmontable pour les tableaux - même si vous pouvez optimiser les insertions, il n'y a rien que vous puissiez faire pour optimiser l'opération de type find-next.

DenNukem
la source
Pourriez-vous s'il vous plaît élaborer ceci: "il est possible de créer une structure de données qui donne une interface d'accès ordonnée de type tableau où la lecture et l'écriture sont, au pire, logarithmiques."
Hengameh
1
Il y a des trucs sur Wikipedia sous la section Dynamic Array / Vriants. Ce n'est pas tout à fait ce que j'avais en tête, cependant ... éléments dans un petit tableau. Lorsque vous insérez un élément dans une page feuille, vous devez déplacer environ la moitié de la page pour faire de la place, puis remonter et mettre à jour le nombre d'éléments sur toutes les pages ancêtres. Lorsque vous recherchez un élément #N, ajoutez simplement le nombre d'éléments de page subordonnés jusqu'à ce que vous
traversiez
3

Dans un tableau, vous avez le privilège d'accéder à n'importe quel élément en temps O (1). Ainsi, il convient pour des opérations telles que la recherche binaire, le tri rapide, etc. La liste liée, d'autre part, convient pour la suppression d'insertion comme dans le temps O (1). Les deux ont des avantages ainsi que des inconvénients et préférer l'un se résume à ce que vous souhaitez mettre en œuvre.

- La plus 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.

pranjal
la source
3

Liste liée

C'est plus préférable quand il s'agit d'insertion! Fondamentalement, ce qui est fait, c'est qu'il traite du pointeur

1 -> 3 -> 4

Insérer (2)

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

finalement

1 -> 2 -> 3 -> 4

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

Facile!

Mais depuis Array

| 1 | 3 | 4 |

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

Eh bien, tout le monde peut visualiser la différence! Juste pour 4 index, nous effectuons 3 étapes

Et si la longueur du tableau est d'un million alors? La baie est-elle efficace? La réponse est non! :)

La même chose vaut pour la suppression! Dans la liste liée, nous pouvons simplement utiliser le pointeur et annuler l'élément et ensuite dans la classe d'objet! Mais pour le tableau, nous devons effectuer shiftLeft ()

J'espère que cela pourra aider! :)

Farah Nazifa
la source
3

La liste liée est plus une surcharge à gérer qu'une baie, elle nécessite également un stockage de mémoire supplémentaire, tous ces points sont convenus. Mais il y a quelques choses que le réseau ne peut pas faire. Dans de nombreux cas, supposons que vous vouliez un tableau de longueur 10 ^ 9, vous ne pouvez pas l'obtenir, car il doit y avoir un emplacement de mémoire continu. La liste liée pourrait être un sauveur ici.

Supposons que vous souhaitiez stocker plusieurs éléments avec des données, elles peuvent ensuite être facilement étendues dans la liste liée.

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

iec2011007
la source
3

1- La liste liée est une structure de données dynamique qui peut donc croître et se réduire au moment de l'exécution en allouant et désallouant de la mémoire. Il n'est donc pas nécessaire de donner une taille initiale de la liste chaînée. L'insertion et la suppression de nœuds sont vraiment plus faciles.

2- La taille de la liste chaînée peut augmenter ou diminuer au moment de l'exécution, il n'y a donc pas de perte de mémoire. Dans le cas du tableau, il y a beaucoup de gaspillage de mémoire, comme si nous déclarons un tableau de taille 10 et y stockons seulement 6 éléments, alors l'espace de 4 éléments est gaspillé. Il n'y a pas un tel problème dans la liste chaînée car la mémoire n'est allouée qu'en cas de besoin.

3- Les structures de données telles que la pile et les files d'attente peuvent être facilement implémentées à l'aide d'une liste chaînée.

Ayman Amjad
la source
2

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

L'inconvénient pourrait être que les pointeurs prennent beaucoup de place.

Et à propos de cela, le codage est plus difficile: Habituellement, vous n'avez pas besoin d'une liste liée de code (ou une seule fois), ils sont inclus dans STL et ce n'est pas si compliqué si vous devez encore le faire.

user15453
la source
2
Les pointeurs prennent beaucoup de place? Pas vraiment. Si vous stockez une liste chaînée de booléens, alors bien sûr, en pourcentage, les pointeurs prennent beaucoup de place. Mais si vous stockez des objets complexes (ce qui est généralement le cas), les pointeurs seraient probablement négligeables.
Herms
oublié le sourire :) Mais a dit "pourrait" pas "est".
user15453
1

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

iram Arshad
la source
1

Selon votre langue, certains de ces inconvénients et avantages pourraient être pris en compte:

Langage de programmation C : lors de l'utilisation d'une liste chaînée (via des pointeurs de structure en général), une attention particulière doit être apportée pour éviter toute fuite de mémoire. Comme cela a été mentionné précédemment, les listes chaînées sont faciles à mélanger, car tout ce qui se faisait est de changer de pointeur, mais allons-nous nous rappeler de tout libérer?

Java : Java a un ramasse-miettes automatique, donc la fuite de mémoire ne sera pas un problème, mais les détails d'implémentation de ce qu'est une liste chaînée sont cachés au programmeur de haut niveau. Des méthodes telles que la suppression d'un nœud du milieu de la liste est une procédure plus compliquée que certains utilisateurs de la langue ne s'y attendent.

SetSlapShot
la source
1

Pourquoi une liste chaînée sur un tableau? Eh bien, comme certains l'ont déjà dit, une plus grande vitesse d'insertions et de suppressions.

Mais peut-être que nous n'avons pas à vivre avec les limites des deux, et à tirer le meilleur parti des deux, en même temps ... hein?

Pour les suppressions de tableau, vous pouvez utiliser un octet «Supprimé», pour représenter le fait qu'une ligne a été supprimée, il n'est donc plus nécessaire de réorganiser le tableau. Pour alléger le fardeau des insertions ou des changements rapides de données, utilisez une liste chaînée pour cela. Ensuite, lorsque vous vous y référez, demandez à votre logique de rechercher d'abord l'un, puis l'autre. Ainsi, leur utilisation en combinaison vous offre le meilleur des deux.

Si vous avez un très grand tableau, vous pouvez le combiner avec un autre tableau beaucoup plus petit ou une liste liée où le plus petit contient les 20, 50, 100 derniers éléments utilisés. Si celui dont vous avez besoin ne se trouve pas dans la liste ou le tableau lié le plus court, vous accédez au grand tableau. S'il y est trouvé, vous pouvez ensuite l'ajouter à la liste / tableau lié plus petit en supposant que `` les choses les plus récemment utilisées sont plus susceptibles d'être réutilisées '' (et oui, peut-être en supprimant l'élément 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û résoudre dans un module de vérification des autorisations de sécurité .ASP, avec facilité, élégance et vitesse impressionnante.

Juan Carlos
la source
1

Alors que beaucoup d'entre vous ont abordé les principaux avantages / différences de la liste chaînée par rapport au tableau, la plupart des comparaisons indiquent comment l'un est meilleur / pire que l'autre. vous pouvez faire un accès aléatoire dans le tableau mais pas possible dans la liste chaînée et autres. Cependant, cela suppose que les listes de liens et les tableaux vont être appliqués dans une application similaire. Cependant, une bonne réponse devrait être de savoir comment la liste de liens serait préférée à la baie et vice-versa dans un déploiement d'application particulier. Supposons que vous souhaitiez implémenter une application de dictionnaire, que feriez-vous? Array: mmm il permettrait une récupération facile grâce à la recherche binaire et à d'autres algo de recherche .. mais laisse penser comment la liste de liens peut être meilleure .. Dites que vous voulez rechercher "Blob" dans le dictionnaire. Serait-il logique d'avoir une liste de liens de A-> B-> C-> D ---->

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

Maintenant, l'approche ci-dessus est-elle meilleure ou un ensemble plat de [Adam, Apple, Banana, Blob, Cat, Cave]? Serait-ce même possible avec array? Ainsi, un avantage majeur de la liste de liens est que vous pouvez avoir un élément non seulement pointant vers l'élément suivant, mais aussi vers une autre liste de liens / tableau / tas / ou tout autre emplacement de mémoire. Le tableau est une mémoire contigüe plate découpée en blocs de la taille de l'élément qu'il va stocker. La liste de liens, d'autre part, est un bloc d'unités de mémoire non contiguës (peut être de n'importe quelle taille et peut stocker n'importe quoi) et pointant vers chacune l'autre comme vous le souhaitez. Disons de même que vous créez une clé USB. Souhaitez-vous maintenant que les fichiers soient enregistrés sous forme de tableau ou de liste de liens? Je pense que vous avez l'idée de ce que je pointe :)

Vikalp Veer
la source