ArrayList vs LinkedList desde la perspectiva de asignación de memoria

Question

Necesito almacenar una gran cantidad de información, por ejemplo, 'nombres' en una lista java. La cantidad de elementos puede cambiar (o en resumen, no puedo predefinir el tamaño). Soy de la opinión de que desde una perspectiva de asignación de memoria LinkedList sería una mejor opción que ArrayList, ya que una ArrayList una vez que se alcanza el tamaño máximo, automáticamente la asignación de memoria se duplica y por lo tanto siempre habrá una posibilidad de asignar más memoria que Qué se necesita.

Entiendo por otras publicaciones aquí que los elementos individuales almacenados en una LinkedList requieren más espacio que una ArrayList ya que LinkedList también necesita almacenar la información del nodo, pero sigo adivinando el escenario que he definido LinkedList podría ser una mejor opción . Además, no quiero entrar en el aspecto de rendimiento (buscar, eliminar, etc.), ya se ha discutido mucho sobre él.

Answer 1

LinkedList podría asignar menos entradas, pero las entradas son astronómicamente más caros de lo que serían para ArrayList - lo suficiente que incluso el peor de los casos es más barato ArrayList en lo que se refiere a la memoria.

(FYI, creo que lo tienes mal; ArrayList crece desde 1,5x cuando está lleno, no 2x.)

Véase, por ejemplo http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures: LinkedList consume 24 bytes por elemento, mientras que ArrayList consume en el mejor de los casos 4 bytes por elemento y, en el peor de los casos, 6 bytes por elemento. (Los resultados pueden variar según las JVM de 32 bits frente a las de 64 bits y las opciones de puntero de objeto comprimido, pero en esas comparaciones LinkedList cuesta al menos 36 bytes/elemento, y ArrayList es como máximo 8 y como mucho 12.)

ACTUALIZACIÓN:

que entiendo de otros mensajes aquí que los elementos individuales almacenados en un LinkedList toma más espacio que un ArrayList como LinkedList también necesita almacenar la información del nodo, pero todavía estoy adivinando para el escenario He definido LinkedList podría ser una mejor opción. Además, no quiero entrar en el aspecto de rendimiento (buscar, eliminar, etc.), ya se ha discutido mucho sobre él.

Para que quede claro, incluso en el peor de los casos , ArrayList es 4x más pequeño que un LinkedList con los mismos elementos. La única forma posible de hacer que LinkedList gane es arreglar deliberadamente la comparación llamando al ensureCapacity con un valor deliberadamente inflado, o eliminar muchos valores del ArrayList después de que se hayan agregado.

En resumen, es básicamente imposible hacer LinkedList ganar la comparación de memoria, y si se preocupan por el espacio, a continuación, llamar trimToSize() en el ArrayList realizará al instante ArrayList victoria de nuevo por un amplio margen. Seriamente. ArrayList gana.

Answer 2

ArrayList.trimToSize() puede satisfacerlo.

Recorta la capacidad de esta instancia ArrayList para ser el tamaño actual de la lista. Una aplicación puede usar esta operación para minimizar el almacenamiento de una instancia de ArrayList.

Por cierto, en ArrayList Java6, no es de doble capacidad, se alcanza un tamaño máximo de 1.5 veces.

Answer 3

ArrayList utiliza una referencia por objeto (o dos cuando tiene el doble de tamaño que necesita) Normalmente es 4 bytes.

LinkedList utiliza solo los nodos que necesita, pero estos pueden tener 24 bytes cada uno.

Por lo tanto, incluso en el peor de los casos ArrayList será 3 veces más pequeño que LinkedList.

Para buscar ARrayList admite acceso aleatorio O (1) pero LinkedList es O (n). Para borrar de la final, ambos son O (1), para borrar de algún lugar en el medio ArrayList es O (n)

A menos que tenga millones de entradas, el tamaño de la colección es poco probable que la materia. Lo que importará primero es el tamaño de las entradas, que es el mismo independientemente de la colección utilizada.

Answer 4

... pero todavía estoy adivinando para el escenario que he definido ListaEnlazada podría ser una mejor opción

Su suposición es incorrecta.

Una vez que haya superado la capacidad inicial de la lista de matrices, el tamaño del respaldo será de entre 1 y 2 referencias multiplicado por el número de entradas. Esto se debe a la estrategia utilizada para hacer crecer la matriz de respaldo.

Para una lista vinculada, cada nodo ocupa POR LO MENOS 3 veces el número de entradas, porque cada nodo tiene una referencia next y prev, así como la referencia de entrada. (Y de hecho, es más de 3 veces, debido al espacio utilizado por los encabezados de objetos y el relleno de los nodos. Dependiendo de la JVM y el tamaño del puntero, puede ser tanto como 6 veces).

El único situación en la que una lista vinculada utilizará menos espacio que una lista de matriz si sobreestima excesivamente la capacidad inicial de la lista de matriz. (Y para listas muy pequeñas ...)

---

Cuando se piensa en ello, la única ventaja real sobre listas enlazadas tienen listas de matriz es cuando se va a insertar y eliminar elementos. Incluso entonces, depende de cómo lo hagas.

Answer 5

parte posterior del sobre del peor caso:

500.000 nombres en una matriz dimensionada para 1000000 = 500000 usado, 500.000 punteros vacíos en la parte no utilizada de la matriz asignado.

500,000 entradas en una lista enlazada = 3 punteros por entrada (el objeto Node tiene actual, anterior y siguiente) = 1,5000,000 punteros en la memoria. (Luego debe agregar el tamaño del Nodo en sí)