¿Hay una lista clasificada indexable en el paquete Java.util?

Question

Estoy buscando una estructura de datos en el paquete java.util. Necesito que cumpla con los siguientes requisitos:

• El número de elementos es (teóricamente) ilimitado.
• Los elementos están ordenados en orden ascendente.
• Puede obtener el enésimo elemento (rápido).
• Puede eliminar el enésimo elemento (rápido).

Esperaba encontrar una lista de salto indexable, pero no fue así. ¿Tienen alguna estructura de datos que cumpla con los requisitos que he indicado?

Answer 1

No existe una estructura de datos simple que cumpla todos sus criterios.

El único que sé que cumple todos ellos sería un indexable skip list. Sin embargo, no sé de ninguna implementación de Java disponible.

Answer 2

Mire PriorityQueue.

Si no necesita elementos similares en su estructura de datos, entonces TreeSet habitual también se ajusta a sus requisitos.

Answer 3

TreeSet le ofrece la funcionalidad de clasificación natural al agregar elementos a la lista. Pero si no lo necesita y Collections.sort() está permitido, puede usar el número ArrayList.

Answer 4

Esta pregunta es muy similar a

• Sorted array list in Java

Para consultar todas my answer to that question.

Básicamente se sugiere lo siguiente:

class SortedArrayList<T> extends ArrayList<T> { 

    @SuppressWarnings("unchecked") 
    public void insertSorted(T value) { 
     add(value); 
     Comparable<T> cmp = (Comparable<T>) value; 
     for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) { 
      T tmp = get(i); 
      set(i, get(i-1)); 
      set(i-1, tmp); 
     } 
    } 
} 

---

una nota en su primer requisito: "El número de elementos no está acotada.":

Es posible que desee limitar este a algo así como "La cantidad de elementos no debe estar limitada por menos de 2 -1 ...", ya que de lo contrario se descartan todas las opciones respaldadas por una matriz Java. (Podría salirse con la suya con una cantidad arbitraria de elementos utilizando, por ejemplo, LinkedList, pero no veo cómo podría hacer búsquedas rápidas en eso.)

Answer 5

Considere List combinado con Collections.sort().

Answer 6

Ir con lo indicado dwb con List<T> y Collections.sort(), se puede utilizar como ArrayList<T> que implementa List<T> (y no se sincroniza como Vector<T> menos por supuesto que desea que los gastos generales). Esa es probablemente la mejor opción porque ellos (Sun) generalmente investigan mucho sobre estas áreas (por lo que he visto de todos modos). Si necesita ordenar por algo que no sea "predeterminado" (es decir, no está ordenando una lista de enteros, etc.), proporcione su propio comparador.

EDIT: La única cosa que no cumplen sus requisitos son los de mudanzas rápido ...

Answer 7

No hay tal recipiente en las bibliotecas estándar de Java.

Cuando necesito una estructura de datos con estas propiedades, uso una aplicación List (generalmente un ArrayList, pero no importa), y hacer todas las inserciones utilizando Collections.binarySearch.

Si tuviera que encapsular una lista ordenada como una clase reutilizable, implementaría la interfaz de lista, delegando todos los métodos en una implementación de lista 'estándar' (incluso puede pasarse como un parámetro al constructor). Implementaría cada método de inserción (add, addAll, set, Iterator's remove) arrojando una excepción (UnsupportedOperationException), para que nadie pueda romper la propiedad 'always sorted'. Finalmente, proporcionaría un método insertSorted que usaría Collections.binarySearch para hacer la inserción.