Quando sai quando utilizzare un TreeSet o LinkedList?

Question

Quali sono i vantaggi di ciascuna struttura?

Nel mio programma ho si esibirà questi passi e mi chiedevo quale struttura dati sopra dovrei usare:

1. Prendendo in un array non ordinato e aggiungendoli a uno structure1 ordinato.
2. Movimento attraverso dati ordinati e rimuovendo quello giusto
3. Aggiunta di dati (mai rimozione) e restituendo quella struttura come un array

Answer 1

Se si desidera mantenere allineati ed è accodare per lo più, TreeSet con un Il comparatore è la soluzione migliore. La JVM dovrebbe attraversare la LinkedList dall'inizio per decidere dove posizionare un oggetto. LinkedList = O (n) per qualsiasi operazione, TreeSet = O (log (n)) per elementi di base.

Answer 2

Quando si sa quando utilizzare un TreeSet o LinkedList? Quali sono i vantaggi di ciascuna struttura?

In generale, si decide un tipo di raccolta in base alle proprietà strutturali e di prestazioni che è necessario avere. Ad esempio, un TreeSet è un Set, quindi non consente duplicati e non conserva l'ordine di inserimento degli elementi. Al contrario, LinkedList è un elenco e pertanto consente duplicati e conserva l'ordine di inserimento. Per quanto riguarda le prestazioni, TreeSet fornisce l'inserimento e la cancellazione di O(logN), mentre LinkedList dà l'inserimento O(1) all'inizio o alla fine e l'inserimento O(N) in una posizione selezionata o la cancellazione.

I dettagli sono tutti specificati nella rispettiva classe e nell'interfaccia javadoc, ma un utile riepilogo può essere trovato nello Java Collections Cheatsheet.

In pratica, tuttavia, la scelta del tipo di raccolta è intimamente connessa alla progettazione dell'algoritmo. I due devono essere fatti in parallelo. (Non è corretto decidere che il tuo algoritmo richieda una collezione con proprietà X, Y e Z, e quindi scoprire che non esiste questo tipo di raccolta.)

Nel tuo caso di utilizzo, sembra che TreeSet sia più adatto . Non esiste un modo efficiente (vale a dire migliore di O(N^2)) per ordinare una grande LinkedList che non implichi la sua conversione in un'altra struttura di dati per l'ordinamento. Non esiste un modo efficace (vale a dire meglio di O(N)) per inserire un elemento nella posizione corretta in una LinkedList ordinata in precedenza. La terza parte (copia su un array) funziona ugualmente bene con un LinkedList o TreeSet; è un'operazione O(N) in entrambi i casi.

[sto supponendo che le collezioni sono abbastanza grandi che il grande O complessità predice le prestazioni effettive con precisione ...]

Answer 3

TreeSet:

TreeSet utilizza albero Rosso-Nero sottostante. Quindi il set potrebbe essere pensato come dynamic search tree. Quando hai bisogno di una struttura che funzioni di lettura/scrittura frequentemente e anche dovrebbe mantenere l'ordine, TreeSet è una buona scelta.

Answer 4

Il vero potere e il vantaggio di TreeSet sta nel interfaccia realizza - NavigableSet

Perché è così potente e in tal caso?

navigabile Set interfaccia aggiungere ad esempio questi 3 metodi curato:

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

Questi metodi consentono di organizzare algoritmo di ricerca efficace (molto veloce).

Esempio: abbiamo bisogno di trovare tutti i nomi che iniziano con Milla e terminare con 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")); 

uscita:

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

TreeSet non va oltre tutti gli elementi, si trova prima e ultima elemenet e restituisce una nuova Collezione con tutti gli elementi della gamma.