1. Accueil
  2. Question et réponse
  3. Quelle implémentation de List utiliser?

Quelle implémentation de List utiliser?

2010-09-30 4 views
7

Dans mon programme, j'utilise souvent des collections pour stocker des listes d'objets. Actuellement, j'utilise ArrayList pour stocker des objets. Ma question est: est-ce un meilleur choix? Peut-être préférable d'utiliser LinkedList? Ou autre chose?Quelle implémentation de List utiliser?

Les critères à prendre en compte sont les suivants:

  • Utilisation de la mémoire
  • Performance

opérations dont j'ai besoin sont:

  • Ajouter un élément à la collection
  • Itérer à travers les éléments

Des pensées?

Mise à jour: mon choix est: ArrayList :) Fonder sur cette discussion, ainsi que les suivantes:

Source

2010-09-30 Andriy Sholokh

+3

Copie possible. http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Fil

+0

Élaborez sur « productivité » s'il vous plaît –

+0

êtes-vous souvent ajouter à la fin de la liste ou à une position arbitraire? –

Répondre

8

I default toujours ArrayList, et serait dans votre cas aussi bien, sauf si

  • J'ai besoin de sécurité de fil (dans ce cas, je commence à regarder la liste des implémentations dans java.util.concurrent)
  • Je sais que je vais faire beaucoup d'insertion et de manipulation à la liste ou le profilage révèle mon utilisation d'un ArrayList pour être un problème (très rare)

Quant à ce qu'il faut choisir dans ce deuxième cas, cette Le fil de SO.com a quelques aperçus utiles: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Source

2010-09-30 13:08:57 whaley

+0

Merci pour le lien vers une discussion très intéressante! –

+0

comment un LinkedList est-il plus sûr pour les threads? – Thilo

+0

@Thilo - Je n'ai jamais dit que c'était. J'ai dit que je par défaut à ArrayList à moins que j'ai besoin de la sécurité de fil. Juste pour le rendre clair, je vais modifier ma réponse pour dire que je vais dans les implémentations de la liste dans java.util.concurrent. – whaley

0

liste liée est plus rapide pour ajouter/enlever les éléments intérieurs (c.-à-d. pas la tête ou la queue)

Arraylist est plus rapide pour l'itération

Source

2010-09-30 13:04:06

+1

Hm. Peut-être que c'est plus rapide en itérant, bien que je ne m'attends pas à ce que ce soit plus que marginal. Le vrai avantage devrait être d'accéder aux éléments dans un ordre aléatoire ... – Dirk

+0

Si je comprends bien les deux ont l'itération O (n). – Qwerky

+0

O (n) itération sur N éléments. L'itérateur de liste liée ne jettera pas si vous lisez ici et changez là-bas ... – GregC

0

C'est un compromis classique entre l'insertion et l'optimisation de récupération. Le choix commun pour la tâche que vous décrivez est le ArrayList.

Source

2010-09-30 13:04:07 GregC

+0

Pourquoi c'est un choix commun? –

+0

Il est rapide d'itérer sur toute la collection, et il y a moins d'espace mémoire car les liens d'une liste liée doivent être stockés quelque part. – GregC

0

ArrayList est bien pour votre (et la plupart des autres) fins. Il a un très léger surcoût de mémoire et une bonne performance amortie pour la plupart des opérations. Les cas où il n'est pas idéal sont relativement rares:

  • La liste ist très grand
  • Vous devez fréquemment faire une de ces opérations:
    • Ajouter/supprimer des éléments lors de l'itération
    • Supprimer des éléments depuis le début de la liste

Source

2010-09-30 13:06:39

+0

Pour développer ce point: l'itérateur de ArrayList lèvera une exception s'il détecte une modification pendant l'itération. En outre, supprimer dès le début une file d'attente est mieux accompli via la liste liée pour des raisons évidentes. – GregC

+0

@GregC: L'itérateur d'un LinkedList ne lance pas d'exceptions lorsqu'il y a des modifications simultanées? Si oui, pourquoi est-ce bon? – Thilo

+0

Il semblerait que je me trompe ... Je devrais essayer ... quoting: "Les itérateurs retournés par les méthodes itérateur et listIterator de cette classe sont fail-fast: si la liste est structurellement modifiée à tout moment après que l'itérateur est créé, de quelque façon que ce soit, à l'exception des méthodes remove ou add de l'Iterator, l'itérateur lève une exception ConcurrentModificationException.Ainsi, face à une modification simultanée, l'itérateur échoue rapidement et proprement, au lieu de risquer un comportement arbitraire et non déterministe indéterminé. – GregC

0

Si vous ne fait qu'ajouter à la fin de la liste, ArrayList devrait aller bien. De la documentation ArrayList:

Les détails de la politique de croissance ne sont pas précisées au-delà du fait que l'ajout d'un élément a le temps amorti constant coût

et ArrayList devrait également utiliser moins de mémoire qu'une liste chaînée car vous n'avez pas besoin d'espace pour les liens.

Source

2010-09-30 13:07:54

0

Cela dépend de votre profil d'utilisation.

Ajoutez-vous à la fin de la liste? Les deux sont bien pour ça. Ajoutez-vous au début de la liste? LinkedList est meilleur pour cela. Avez-vous besoin d'un accès aléatoire (appelez-vous jamais get(n) dessus)? ArrayList est meilleur pour cela.

Les deux sont bons à itérer les deux implémentations sont Iterator O (1) pour next().

En cas de doute, tester votre application à chaque mise en œuvre et de faire votre choix.

Source

2010-09-30 13:18:00 Qwerky

0

Je sais que je suis en retard mais, peut-être, this page peut vous aider, non seulement maintenant, mais à l'avenir ...

Source

2010-09-30 13:21:00 SoulWanderer

0

Compte tenu de vos critères, vous devriez utiliser la LinkedList.

LinkedList implémente l'interface Deque ce qui signifie qu'il peut ajouter au début ou à la fin de la liste en temps constant (1). De plus, ArrayList et LinkedList parcourront l'heure (N).

Vous ne devriez pas utiliser le ArrayList simplement parce que le coût de l'ajout d'un élément lorsque la liste est complète. Dans ce cas, l'ajout de l'élément serait (N) en raison de la création du nouveau tableau et de la copie de tous les éléments d'un tableau à l'autre.

En outre, le ArrayList prendra plus de mémoire parce que la taille de votre tableau de sauvegarde pourrait ne pas être complètement rempli.

Source

2010-09-30 15:55:41 javaman

+0

Mon collègue vient d'écrire un test simple - ajouter des éléments à des listes de différentes tailles dans différents endroits. Et voici le résultat: J'ai fait mon propre test sans prétention. Voici le résultat: - Ajout simple (List.add ("A")): ArrayList plus rapide que LinkedList 3-5 temps sur une plage de taille de 1 à 100 000. –

+0

Ajouter à la tête de liste (List.add (0, "A"): A la taille 1, le temps est égal à la taille 100 LinkedList plus rapide ~ 2 fois; Au format 1000 LinkedList plus rapide ~ 10 fois; Au format 10000 LiskedList plus rapide ~ 50 fois; Au format 50000 LinkedList plus rapide ~ 80 times –

+0

Ajout aléatoire (List.add (Math.random (list.size()), "A")): ArrayList plus rapidement que LinkedList 2 fois sur la même plage (1 à 100 000) –

Questions connexes

 Questions connexes