Adrián, parte de nuestro equipo, nos hizo el favor de escribir este artículo porque controla perfectamente el tema.
Solución:
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 es más barato en lo que a memoria se refiere.
(Para su información, creo que lo entendió mal; ArrayList crece 1,5 veces cuando está lleno, no 2 veces).
Véase, por ejemplo, https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt: 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 en el mejor de los casos 8 y en el peor 12.)
ACTUALIZAR:
Entiendo por otras publicaciones aquí que los elementos individuales almacenados en una LinkedList ocupan más espacio que una ArrayList, ya que LinkedList también necesita almacenar la información del nodo, pero sigo suponiendo que el escenario que he definido LinkedList podría ser una mejor opción. Además, no quiero entrar en el aspecto del rendimiento (recuperación, eliminación, etc.), ya que ya se ha discutido mucho al respecto.
Para ser claro, incluso en el peor de los casos, ArrayList es 4 veces más pequeño que un LinkedList con los mismos elementos. La única manera posible de hacer LinkedList ganar es arreglar deliberadamente la comparación llamando ensureCapacity con un valor deliberadamente inflado, o para eliminar muchos valores de la ArrayList después de que se hayan agregado.
En resumen, es básicamente imposible hacer LinkedList gana la comparación de memoria, y si te importa el espacio, llama trimToSize() sobre el ArrayList instantáneamente hará ArrayList ganar de nuevo por un amplio margen. En serio. ArrayList gana
… pero todavía estoy adivinando que el escenario que he definido LinkedList podría ser una mejor opción
Tu conjetura es incorrecta.
Una vez superada la capacidad inicial del array lista, el tamaño del respaldo será entre 1 y 2 referencias por el número de entradas. Esto se debe a la estrategia utilizada para hacer crecer el respaldo. array.
Para una lista enlazada, cada nodo ocupa AL MENOS 3 veces el número de entradas, porque cada nodo tiene un next y prev referencia, así como la referencia de entrada. (Y, de hecho, es más de 3 veces, debido al espacio utilizado por los encabezados y el relleno de los objetos de los nodos. Según la JVM y el tamaño del puntero, puede ser hasta 6 veces).
La única situación en la que una lista enlazada utilizará menos espacio que una array lista es si sobreestimas gravemente el array capacidad inicial de la lista. (Y para listas muy pequeñas…)
Cuando lo piensa, la única ventaja real que tienen las listas vinculadas sobre array las listas es cuando está insertando y eliminando elementos. Incluso entonces, depende de cómo lo hagas.
ArrayList.trimToSize() puede satisfacerlo.
Recorta la capacidad de esta instancia de ArrayList para que tenga 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 se duplica la capacidad, se alcanza aproximadamente 1,5 veces el tamaño máximo.
Puntuaciones y reseñas
Te invitamos a añadir valor a nuestro contenido dando tu experiencia en las explicaciones.