java - entre - linkedlist vs list

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 LinkedList toman más espacio que ArrayList ya que LinkedList también necesita almacenar la información del nodo, pero todavía estoy adivinando para 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

... pero sigo adivinando el escenario que he definido, LinkedList podría ser una mejor opción

Tu conjetura es incorrecta.

Una vez que haya superado la capacidad inicial de la lista de arreglos, el tamaño del respaldo estará 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).

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

Cuando lo piensas, la única ventaja que las listas vinculadas tienen sobre las listas de arreglos es cuando estás insertando y eliminando elementos. Incluso entonces, depende de cómo lo hagas.

Answer 2

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

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

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

Para recuperar ARrayList admite acceso aleatorio O (1) pero LinkedList es O (n). Para eliminar desde el final, ambos son O (1), para eliminar desde algún lugar en el medio ArrayList es O (n)

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

Answer 3

Detrás del sobre el peor de los casos:

500,000 nombres en una matriz de tamaño de 1,000,000 = 500,000 utilizados, 500,000 punteros vacíos en la porción no utilizada de la matriz asignada.

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. (Entonces tienes que agregar el tamaño del Nodo en sí)

Answer 4

ArrayList.trimToSize() puede satisfacerte.

Recorta la capacidad de esta instancia de 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 5

LinkedList podría asignar menos entradas, pero esas entradas son astronómicamente más caras de lo que serían para ArrayList , lo suficiente como para que incluso el peor de los casos ArrayList sea ​​más barato en lo que respecta a la memoria.

(Para su información, creo que está equivocado, ArrayList crece en 1.5x cuando está lleno, no en 2x).

Ver, 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 está en el mejor de 8 y en el peor de los 12).

ACTUALIZAR:

Entiendo por otras publicaciones aquí que los elementos individuales almacenados en LinkedList toman más espacio que ArrayList ya que LinkedList también necesita almacenar la información del nodo, pero todavía estoy adivinando para 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.

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

En resumen, es básicamente imposible hacer que LinkedList gane la comparación de memoria, y si te preocupa el espacio, entonces llamando a trimToSize() en ArrayList instantáneamente hará que ArrayList gane nuevamente por un gran margen. Seriamente. ArrayList gana.