Implementación de listas que mantiene el orden.

Hay una existenteList Implementación en Java que mantiene el orden basado en lo proporcionado.Comparator?

Algo que se puede utilizar de la siguiente manera:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

así que esosomeT se inserta de tal manera que el orden en la lista se mantiene de acuerdo concmp

(En la sugerencia de @andersoj, estoy completando mi pregunta con una solicitud más)

También quiero poder recorrer la lista en orden ordenado sin eliminar los elementos, es decir:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

debe pasar

Todas las sugerencias son bienvenidas (excepto que me diga que useCollections.sort en la lista completa no ordenada), sin embargo, preferiría algo enjava.* o eventualmenteorg.apache.* Ya que sería difícil introducir nuevas bibliotecas en este momento.

Nota: (ACTUALIZACIÓN 4) Me di cuenta de que las implementaciones de este tipo de lista tendrían un rendimiento inadecuado. Hay dos enfoques generales:

Usar estructura vinculada (tipo de) árbol B o similarUtilizar matriz e inserción (con búsqueda binaria)

No 1. tiene problemas con la memoria caché de la CPU. No 2. tiene problemas con el desplazamiento de elementos en la matriz.

ACTUALIZACIÓN2: TreeSet no funciona porque usa el comparador provisto (MyComparator) para verificar la igualdad y, en base a ello, supone que los elementos son iguales y los excluye. Necesito ese comparador solo para ordenar, no para el filtrado de "unicidad" (ya que los elementos por su orden natural no son iguales)

ACTUALIZACIÓN3: PriorityQueue no funciona comoList (ya que lo necesito) porque no hay manera de atravesarlo en el orden en que está "ordenado", para obtener los elementos en el orden ordenado, debe eliminarlos de la colección.

ACTUALIZAR:

Pregunta similar:
Una buena lista ordenada para Java
Lista ordenada de la matriz en Java