¿Cuándo sabe cuándo usar TreeSet o LinkedList?

Question

¿Cuáles son las ventajas de cada estructura?

En mi programa que va a realizar estos pasos y me preguntaba qué estructura de datos anteriores que debería usar:

1. Tomando en una matriz sin clasificar y añadirlas a una Structure1 ordenada.
2. Atravesando través de datos ordenados y la eliminación de la correcta
3. Adición de datos (nunca eliminación) y devolver esa estructura como una matriz

Answer 1

Si desea mantener lo resuelto y es anexar su mayoría, TreeSet con una Comparador es su mejor apuesta. La JVM tendría que atravesar LinkedList desde el principio para decidir dónde colocar un elemento. LinkedList = O (n) para cualquier operación, TreeSet = O (log (n)) para cosas básicas.

Answer 2

¿Cuándo sabe cuándo usar TreeSet o LinkedList? ¿Cuáles son las ventajas de cada estructura?

En general, usted elige un tipo de colección basado en las propiedades estructurales y de rendimiento que necesita. Por ejemplo, un TreeSet es un conjunto, y por lo tanto no permite duplicados y no conserva el orden de inserción de los elementos. Por el contrario, LinkedList es una lista y, por lo tanto, permite duplicados y conserva el orden de inserción. Por el lado del rendimiento, TreeSet le da O(logN) inserción y eliminación, mientras que LinkedList da la inserción O(1) al comienzo o al final, y la inserción O(N) en una posición seleccionada o eliminación.

Los detalles están detallados en la clase e interfaz javadocs respectivas, pero se puede encontrar un resumen útil en el Java Collections Cheatsheet.

En la práctica, la elección del tipo de colección está íntimamente relacionada con el diseño del algoritmo. Los dos deben hacerse en paralelo. (No es bueno decidir que su algoritmo requiere una colección con las propiedades X, Y y Z, y luego descubrir que no existe tal tipo de colección.)

En su caso de uso, parece que TreeSet sería un mejor ajuste . No existe una forma eficiente (es decir, mejor que O(N^2)) para ordenar una lista enlazada grande que no implique convertirla en otra estructura de datos para hacer la ordenación. No hay una forma eficiente (es decir, mejor que O(N)) para insertar un elemento en la posición correcta en una LinkedList previamente clasificada. La tercera parte (copiar en una matriz) funciona igualmente bien con LinkedList o TreeSet; es una operación O(N) en ambos casos.

[Estoy asumiendo que las colecciones son lo suficientemente grandes que la gran complejidad de O predice con precisión el rendimiento real ...]

Answer 3

TreeSet:

TreeSet utiliza árbol Red-Negro subyacente. Por lo tanto, el conjunto podría considerarse como dynamic search tree. Cuando necesite una estructura que funcione con lectura/escritura con frecuencia y también debe mantener el orden, TreeSet es una buena opción.

Answer 4

El verdadero poder y la ventaja de TreeSet se encuentra en la interfaz que se da cuenta - NavigableSet

Por qué es tan potente y en este caso?

interfaz navegable Conjunto añadir, por ejemplo, estos 3 métodos bonito:

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

Estos métodos permiten organizar algoritmo de búsqueda efectiva (muy rápido).

Ejemplo: tenemos que encontrar todos los nombres que empiezan por Milla y terminar 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")); 

de salida:

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

TreeSet no va más de todos los elementos, se encuentra primer y último elemenets y devuelve una nueva colección con todos los elementos del rango.