Quand savez-vous quand utiliser TreeSet ou LinkedList?

Question

Quels sont les avantages de chaque structure?

Dans mon programme je vais être l'exécution de ces étapes et je me demandais quelle structure de données ci-dessus, je devrais utiliser:

1. Prendre dans un tableau non trié et les ajoutant à une Structure1 triée.
2. Traversant par des données triées et retrait de la droite
3. Ajout de données (jamais enlever) et le retour de cette structure comme un tableau

Answer 1

Si vous voulez le garder triée et il est append la plupart du temps, TreeSet avec Le comparateur est votre meilleur pari. La JVM devrait traverser la LinkedList depuis le début pour décider où placer un objet. LinkedList = O (n) pour toutes les opérations, TreeSet = O (log (n)) pour les choses de base.

Answer 2

Quand savez-vous quand utiliser TreeSet ou LinkedList? Quels sont les avantages de chaque structure?

En général, vous décidez d'un type de collection en fonction des propriétés structurelles et de performances dont vous avez besoin. Par exemple, un TreeSet est un Set, et par conséquent n'autorise pas les doublons et ne conserve pas l'ordre d'insertion des éléments. En revanche, LinkedList est une liste et autorise donc les doublons et conserve l'ordre d'insertion. Du côté des performances, TreeSet vous donne l'insertion et la suppression O(logN), tandis que LinkedList donne l'insertion O(1) au début ou à la fin, et l'insertion O(N) à une position ou une suppression sélectionnée.

Les détails sont tous épelés dans la classe et l'interface javadocs respectives, mais un résumé utile peut être trouvé dans le Java Collections Cheatsheet.

En pratique cependant, le choix du type de collection est intimement lié à la conception de l'algorithme. Les deux doivent être faits en parallèle. (Il n'est pas bon de décider que votre algorithme nécessite une collection avec les propriétés X, Y et Z, puis de découvrir qu'aucun tel type de collection n'existe.)

Dans votre cas d'utilisation, il semble que TreeSet conviendrait mieux . Il n'existe pas de moyen efficace (c'est-à-dire meilleur que O(N^2)) pour trier une LinkedList volumineuse qui n'implique pas de la transformer en une autre structure de données pour effectuer le tri. Il n'existe aucun moyen efficace (c'est-à-dire meilleur que O(N)) pour insérer un élément dans la position correcte dans une liste LinkedList préalablement triée. La troisième partie (copie à un tableau) fonctionne aussi bien avec LinkedList ou TreeSet; c'est une opération O(N) dans les deux cas.

[Je suppose que les collections sont assez grand que la grande complexité O prédit avec précision les performances réelles ...]

Answer 3

TreeSet:

TreeSet utilise l'arbre rouge-noir sous-jacent. Donc, l'ensemble pourrait être considéré comme dynamic search tree. Lorsque vous avez besoin d'une structure qui fonctionne souvent en lecture/écriture et qui doit également rester en ordre, TreeSet est un bon choix.

Answer 4

La puissance réelle et l'avantage de TreeSet se trouve dans l'interface, il se rend compte - NavigableSet

Pourquoi est-il si puissant et dans ce cas?

set interface Navigable ajouter par exemple ces 3 méthodes agréable:

headSet(E toElement, boolean inclusive) 
    tailSet(E fromElement, boolean inclusive) 
    subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) 

Ces méthodes permettent d'organiser l'algorithme de recherche efficace (très rapide).

Exemple: nous devons trouver tous les noms qui commencent par Milla et se terminent par Wladimir:

TreeSet<String> authors = new TreeSet<String>(); 
    authors.add("Andreas Gryphius"); 
    authors.add("Fjodor Michailowitsch Dostojewski"); 
    authors.add("Alexander Puschkin"); 
    authors.add("Ruslana Lyzhichko"); 
    authors.add("Wladimir Klitschko"); 
    authors.add("Andrij Schewtschenko"); 
    authors.add("Wayne Gretzky"); 
    authors.add("Johann Jakob Christoffel"); 
    authors.add("Milla Jovovich"); 
    authors.add("Taras Schewtschenko"); 
    System.out.println(authors.subSet("Milla", "Wladimir")); 

sortie:

[Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky] 

TreeSet ne va pas sur tous les éléments, il trouve premier et dernier elemenets et retourne une nouvelle collection avec tous les éléments de la gamme.