¿Qué implementación de List usar?

En mi programa, suelo usar colecciones para almacenar listas de objetos. Actualmente utilizo ArrayList para almacenar objetos. Mi pregunta es: ¿es esta la mejor opción? ¿Puede ser mejor usar LinkedList? ¿O algo mas?¿Qué implementación de List usar?

criterios a considerar son:

Uso de memoria
Rendimiento

Operaciones que necesito son:

Añadir elemento a la colección
recorrer los elementos

¿Alguna idea?

Actualización: mi elección es: ArrayList :) Basándose en este análisis, así como los siguientes:

Fuente

2010-09-30 Andriy Sholokh

Posible duplicado. http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Fil

Elabore sobre "Productividad" por favor –

¿Está agregando principalmente al final de la lista o en cualquier posición arbitraria? –

Siempre DEFAULT para ArrayList, y lo haría en su caso también, excepto cuando

necesito hilo de seguridad (en cuyo caso, empezar a buscar en la Lista implementaciones en java.util.concurrent)
sé que voy a estar haciendo un montón de inserción y la manipulación de la Lista o perfilado revela mi uso de un ArrayList a ser un problema (muy raro)

en cuanto a lo de recoger en ese segundo caso, esta La secuencia de SO.com tiene algunas ideas útiles: List implementations: does LinkedList really perform so poorly vs. ArrayList and TreeList?

Fuente

2010-09-30 13:08:57 whaley

¡Gracias por el enlace a una discusión muy interesante! –

¿cómo es una LinkedList más segura para subprocesos? – Thilo

@Thilo - Nunca dije que fuera. Dije que de manera predeterminada ArrayList a menos que necesite seguridad de subprocesos. Solo para dejarlo en claro, modificaré mi respuesta para decir que voy a las implementaciones de List en java.util.concurrent. – whaley

lista Vinculado es más rápido para añadir/eliminación de elementos internos (es decir, no cabeza o cola)

Arraylist es más rápido para iterar

Fuente

2010-09-30 13:04:06

Hm. Tal vez sea más rápido al iterar, aunque no espero que sea más que marginal. El beneficio real debería ser acceder a los elementos en orden aleatorio ... – Dirk

Según tengo entendido, ambos tienen O (n) iteración. – Qwerky

O (n) iteración sobre N elementos. El iterador de la lista enlazada no se lanzará si lee aquí y cambia de lugar allí ... – GregC

Es una clásica solución de compromiso entre la inserción frente a la optimización de recuperación. La opción común para la tarea tal como la describe es ArrayList.

Fuente

2010-09-30 13:04:07 GregC

¿Por qué es una opción común? –

Es rápido para iterar sobre toda la colección, y hay menos huella de memoria ya que los enlaces en una lista vinculada deben almacenarse en algún lugar. – GregC

ArrayList está bien para sus fines (y la mayoría de los demás). Tiene una sobrecarga de memoria muy pequeña y tiene un buen rendimiento amortizado para la mayoría de las operaciones. Los casos en los que no es lo ideal son relativamente raros:

La lista ist muy grande
Con frecuencia se necesita hacer una de estas operaciones:
- Agregar/eliminar elementos durante la iteración
- en Eliminar elementos desde el comienzo de la lista

Fuente

2010-09-30 13:06:39

Para explicar más sobre este punto: el iterador de ArrayList arrojará una excepción si detecta cambios durante la iteración. Además, eliminar desde el principio a la cola se logra mejor a través de la lista vinculada por razones obvias. – GregC

@GregC: ¿un iterador de LinkedList no arroja excepciones cuando hay modificaciones concurrentes? Si es así, ¿por qué es eso bueno? – Thilo

Parece que estoy equivocado ... Tendré que intentarlo ... citando: "Los iteradores devueltos por el iterador de esta clase y los métodos listIterator son rápidos: si la lista se modifica estructuralmente en cualquier momento después de que el iterador esté creado, de cualquier forma excepto a través de los propios métodos remove o add del iterador, el iterador generará una ConcurrentModificationException. Por lo tanto, frente a una modificación concurrente, el iterador falla rápida y limpiamente, en lugar de arriesgarse a un comportamiento arbitrario no determinista en una forma indeterminada tiempo en el futuro. " – GregC

Si sólo está añadiendo al final de la lista, ArrayList debería estar bien. A partir de la documentación de ArrayList:

Los detalles de la política de crecimiento no se especifican más allá del hecho de que la adición de un elemento tiene constante de tiempo el coste amortizado

y ArrayList también debería usar menos memoria que una lista enlazada ya que no necesita usar espacio para los enlaces.

Fuente

2010-09-30 13:07:54

Depende de su perfil de uso.

¿Agregas al final de la lista? Ambos están bien para esto. ¿Agregas al comienzo de la lista? LinkedList es mejor para esto. ¿Necesita acceso aleatorio (alguna vez llamará al get(n))? ArrayList es mejor para esto.

Ambos son buenos para iterar, ambas implementaciones de Iterator son O (1) para next().

En caso de duda, pruebe su propia aplicación con cada implementación y haga su propia elección.

Fuente

2010-09-30 13:18:00 Qwerky

Sé que voy tarde, pero, tal vez, this page puede ayudar, no sólo ahora, sino en el futuro ...

Fuente

2010-09-30 13:21:00 SoulWanderer

supongo que esto sería un buen comienzo: http://www.odi.ch/prog/design/newbies.php#26 Muestra diferencias en el rendimiento de diferentes implementaciones de List.

Fuente

2010-09-30 14:17:19

Teniendo en cuenta sus criterios, debe utilizar LinkedList.

LinkedList implementa la interfaz Deque, lo que significa que puede agregarse al inicio o al final de la lista en tiempo constante (1). Además, ArrayList y LinkedList iterarán en (N) tiempo.

NO debe utilizar ArrayList simplemente porque el costo de agregar un elemento cuando la lista está llena. En este caso, agregar el elemento sería (N) debido a la nueva matriz que se está creando y copiando todos los elementos de una matriz a la otra.

Además, ArrayList ocupará más memoria porque el tamaño de la matriz de respaldo podría no estar completamente lleno.

Fuente

2010-09-30 15:55:41 javaman

Mi colega acaba de escribir una prueba simple: agrega elementos a listas de diferentes tamaños en diferentes lugares. Y aquí está el resultado: He hecho mi propia prueba sin pretensiones. Aquí está el resultado: - Adición simple (List.add ("A")): ArrayList más rápido que LinkedList 3-5 veces en el rango de tamaño de 1 a 100 000. –

Agregando al encabezado de la lista (List.add (0, "A"): en el tamaño 1 el tiempo es igual; en el tamaño 100 LinkedList más rápido ~ 2 veces; en el tamaño 1000 LinkedList más rápido ~ 10 veces; en el tamaño 10000 LiskedList más rápido ~ 50 veces; en el tamaño 50000 LinkedList faster ~ 80 veces –

Agregar aleatoriamente (List.add (Math.random (list.size()), "A")): ArrayList más rápido que LinkedList 2 veces en el mismo rango (1 a 100 000) –

¿Qué implementación de List usar?

Respuesta

Cuestiones relacionadas