¿ArrayList o LinkedList son mejores para ordenar?

Quiero utilizar la estructura de datos que debe ordenarse de vez en cuando. El tamaño de la estructura de datos apenas superará los 1000 elementos.

¿Cuál es mejor – ArrayList o LinkedList ?

¿Qué algoritmo de clasificación es mejor usar?

Hasta Java 7, no importaba porque Collections.sort volcaría el contenido de la lista en una matriz.

Con Java 8, el uso de un ArrayList debería ser un poco más rápido porque Collections.sort llamará a List.sort y ArrayList tiene una versión especializada que ordena la matriz de respaldo directamente, guardando una copia.

Por lo tanto, la conclusión es que ArrayList es mejor, ya que ofrece un rendimiento similar o mejor según la versión de Java.

Si va a utilizar java.util.Collections.sort(List) entonces realmente no importa.

Si la List no implementa RandomAccess , entonces será volcado a una List La lista se descargará en una matriz para propósitos de clasificación de todos modos.

(Gracias por mantenerme honesto, Ralph. Parece que confundí las implementaciones de orden y barajadas. Están lo suficientemente cerca de lo mismo, ¿no?)

Si puede usar la biblioteca Apache, eche un vistazo a TreeList . Soluciona tu problema correctamente.

Sólo 1000 artículos? ¿Por qué te importa?

Por lo general, siempre uso ArrayList a menos que tenga una necesidad específica de hacer lo contrario.

Eche un vistazo al código fuente. Creo que la clasificación se basa en matrices de todos modos, si recuerdo correctamente.

Si solo está ordenando y no está actualizando dinámicamente su lista ordenada, entonces cualquiera de los dos está bien y una matriz será más eficiente en memoria. Las listas enlazadas son realmente mejores si desea mantener una lista ordenada. Insertar un objeto es rápido en el medio de una lista vinculada, pero lento en una matriz.

Las matrices son mejores si quieres encontrar un objeto en el medio. Con una matriz, puede hacer una ordenación binaria y buscar si un miembro está en la lista en tiempo O (logN). Con una lista vinculada, debe recorrer la lista completa, que es muy lenta.

Supongo que lo que es mejor para tu aplicación depende de lo que quieras hacer con la lista una vez que esté ordenada.

    Intereting Posts