Siempre he sido de los que simplemente usan:
List<String> names = new ArrayList<>();Utilizo la interfaz como nombre de tipo para portabilidad para que cuando haga preguntas como estas pueda reelaborar mi código.
¿Cuándo debería LinkedList ser utilizado sobre ArrayList y viceversa?
Resumen ArrayList con ArrayDeque son preferibles en muchos más casos de uso que LinkedList . Si no está seguro, empiece por ArrayList .
TLDR, en ArrayList acceder a un elemento lleva un tiempo constante [O(1)] y añadir un elemento lleva un tiempo O(n) [en el peor de los casos]. En LinkedList, añadir un elemento lleva un tiempo O(n) y acceder a él también lleva un tiempo O(n), pero LinkedList utiliza más memoria que ArrayList.
LinkedList y ArrayList son dos implementaciones diferentes de la interfaz List. LinkedList lo implementa con una lista doblemente enlazada. ArrayList lo implementa con un Array que se redimensiona dinámicamente.
Al igual que con las operaciones estándar de listas enlazadas y arrays, los distintos métodos tendrán tiempos de ejecución algorítmica diferentes.
Para LinkedList<E>
get(int index) es O(n) (con n/4 pasos en promedio), pero O(1) cuando index = 0 o index = list.size() - 1 (en este caso, también puede utilizar getFirst() y getLast() ). Uno de los principales beneficios de LinkedList<E>add(int index, E element) es O(n) (con n/4 pasos en promedio), pero O(1) cuando index = 0 o index = list.size() - 1 (en este caso, también puede utilizar addFirst() y addLast() / add() ). Uno de los principales beneficios de LinkedList<E>remove(int index) es O(n) (con n/4 pasos en promedio), pero O(1) cuando index = 0 o index = list.size() - 1 (en este caso, también puede utilizar removeFirst() y removeLast() ). Uno de los principales beneficios de LinkedList<E>Iterator.remove() es O(1) . Uno de los principales beneficios de LinkedList<E>ListIterator.add(E element) es O(1) . Uno de los principales beneficios de LinkedList<E>Nota: Muchas de las operaciones necesitan n/4 pasos de media, constante número de pasos en el mejor de los casos (por ejemplo, índice = 0), y n/2 pasos en el peor de los casos (la mitad de la lista)
Para ArrayList<E>
get(int index) es O(1) . Principal beneficio de ArrayList<E>add(E element) es O(1) amortizado, pero O(n) en el peor de los casos, ya que el Array debe ser redimensionado y copiadoadd(int index, E element) es O(n) (con n/2 pasos de media)remove(int index) es O(n) (con n/2 pasos de media)Iterator.remove() es O(n) (con n/2 pasos de media)ListIterator.add(E element) es O(n) (con n/2 pasos de media)Nota: Muchas de las operaciones necesitan n/2 pasos de media, constante número de pasos en el mejor de los casos (fin de la lista), n pasos en el peor de los casos (inicio de la lista)
LinkedList<E> permite realizar inserciones o extracciones en tiempo constante utilizando iteradores pero sólo el acceso secuencial de los elementos. En otras palabras, se puede recorrer la lista hacia delante o hacia atrás, pero encontrar una posición en la lista lleva un tiempo proporcional al tamaño de la lista. Javadoc dice "las operaciones que indexan en la lista recorrerán la lista desde el principio o el final, lo que esté más cerca" Así que esos métodos son O(n) ( n/4 pasos) en promedio, aunque O(1) para index = 0 .
ArrayList<E> por otro lado, permiten un rápido acceso de lectura aleatorio, por lo que se puede coger cualquier elemento en tiempo constante. Pero añadir o eliminar desde cualquier lugar que no sea el final requiere desplazar todos los últimos elementos, ya sea para hacer una abertura o rellenar el hueco. Además, si añades más elementos que la capacidad de la matriz subyacente, se asigna una nueva matriz (1,5 veces el tamaño), y la matriz antigua se copia en la nueva, por lo que añadir a una matriz ArrayList es O(n) en el peor de los casos, pero constante en la media.
Así que dependiendo de las operaciones que pretendas hacer, deberás elegir las implementaciones en consecuencia. Iterar sobre cualquiera de los dos tipos de Lista es prácticamente igual de barato. (Iterar sobre una ArrayList es técnicamente más rápido, pero a menos que estés haciendo algo realmente sensible al rendimiento, no deberías preocuparte por esto - ambos son constantes).
Las principales ventajas de utilizar un LinkedList surgen cuando se reutilizan los iteradores existentes para insertar y eliminar elementos. Estas operaciones se pueden realizar en O(1) cambiando la lista sólo localmente. En una lista de Array, el resto del Array necesita ser movido (es decir, copiado). Por otro lado, buscar en un LinkedList significa seguir los enlaces en O(n) ( n/2 pasos) para el peor de los casos, mientras que en un ArrayList la posición deseada se puede calcular matemáticamente y acceder a ella en O(1) .
Otra ventaja de utilizar un LinkedList surge cuando se agrega o elimina de la cabeza de la lista, ya que esas operaciones son O(1) mientras que ellos son O(n) para ArrayList . Tenga en cuenta que ArrayDeque puede ser una buena alternativa a LinkedList para añadir y quitar de la cabeza, pero no es un List .
Además, si tienes listas grandes, ten en cuenta que el uso de la memoria también es diferente. Cada elemento de una lista LinkedList tiene más sobrecarga, ya que también se almacenan los punteros a los elementos siguientes y anteriores. ArrayLists no tienen esta sobrecarga. Sin embargo, ArrayLists ocupan toda la memoria asignada para la capacidad, independientemente de que se hayan añadido realmente elementos.
La capacidad inicial por defecto de un ArrayList es bastante pequeño (10 de Java 1.4 - 1.8). Pero como la implementación subyacente es un Array, el Array debe ser redimensionado si añades muchos elementos. Para evitar el alto coste de redimensionar cuando sabes que vas a añadir muchos elementos, construye el ArrayList con una mayor capacidad inicial.
Si se utiliza la perspectiva de las estructuras de datos para entender las dos estructuras, una LinkedList es básicamente una estructura de datos secuencial que contiene un Nodo de cabecera. El Nodo es una envoltura para dos componentes: un valor de tipo T [aceptado a través de los genéricos] y otra referencia al Nodo vinculado a él. Por tanto, podemos afirmar que es una estructura de datos recursiva (un Nodo contiene otro Nodo que tiene otro Nodo y así sucesivamente...). La adición de elementos toma un tiempo lineal en LinkedList como se ha dicho anteriormente.
Un ArrayList, es un Array que puede crecer. Es igual que un Array normal. Cuando se añade un elemento en el índice i, se crea otro Array con un tamaño que es 1 mayor que el tamaño anterior (así que en general, cuando se añaden n elementos a un ArrayList, se crea un nuevo Array de tamaño anterior más n). A continuación se copian los elementos del Array anterior al nuevo y los elementos que se van a añadir se colocan también en los índices especificados.
Una cosa que mucha gente olvida es que ArrayList es compacto en memoria, lo que significa que es más amigable con la caché que LinkedList. LinkedList puede estar esparcida por toda la RAM, mientras que ArrayList está siempre bien empaquetada para aprovechar la localidad espacial. Esto tiene importantes ramificaciones en el mundo real.
¿Sacar un elemento del final de ArrayList<E> tendría una complejidad de tiempo constante? Ya que creo que no requiere ningún desplazamiento de elementos? Ej. index = list.size() - 1. remove(index)
Hasta ahora, nadie parece haber abordado la huella de memoria de cada una de estas listas, además del consenso general de que un LinkedList es "mucho más" que un ArrayList así que hice algunos cálculos para demostrar exactamente cuánto ocupan ambas listas para N referencias nulas.
Dado que las referencias son de 32 o 64 bits (incluso cuando son nulas) en sus sistemas relativos, he incluido 4 conjuntos de datos para 32 y 64 bits LinkedLists y ArrayLists .
Nota: Los tamaños indicados para el ArrayList las líneas son para listas recortadas - En la práctica, la capacidad del Array de respaldo en un ArrayList es generalmente mayor que su número de elementos actual.
Nota 2: (gracias BeeOnRope) Como CompressedOops es por defecto ahora desde mediados de JDK6 y arriba, los valores de abajo para las máquinas de 64 bits básicamente coincidirán con sus contrapartes de 32 bits, a menos, por supuesto, que usted específicamente lo desactive.
El resultado muestra claramente que LinkedList es mucho más que ArrayList especialmente con un número de elementos muy elevado. Si la memoria es un factor, evite los LinkedLists .
Las fórmulas que utilicé son las siguientes, avísame si he hecho algo mal y lo arreglaré. 'b' es 4 u 8 para sistemas de 32 o 64 bits, y 'n' es el número de elementos. La razón de los mods es porque todos los objetos en java ocuparán un múltiplo de 8 bytes de espacio independientemente de que se utilicen todos o no.
ArrayList:
ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)
LinkedList:
LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
El problema de tus matemáticas es que tu gráfico exagera mucho el impacto. Estás modelando objetos que contienen cada uno sólo un int , es decir, 4 u 8 bytes de datos. En la lista enlazada, hay esencialmente 4 "palabras" de sobrecarga. Por lo tanto, su gráfico da la impresión de que las listas enlazadas utilizan "cinco veces" el almacenamiento de las listas Array. Esto es un error. La sobrecarga es de 16 o 32 bytes por objeto, como un ajuste aditivo, no un factor de escala.
ArrayList es lo que quieres. LinkedList es casi siempre un error (de rendimiento).
Por qué LinkedList es un asco:
ArrayList se utilizó.ArrayList De todos modos, es probable que sea significativamente más lento.LinkedList en la fuente porque probablemente sea la opción equivocada.
Como alguien que ha estado haciendo ingeniería de rendimiento operacional en servicios web SOA a muy gran escala durante una década, preferiría el comportamiento de LinkedList sobre ArrayList. Mientras que el rendimiento en estado estacionario de LinkedList es peor y, por lo tanto, podría conducir a la compra de más hardware, el comportamiento de ArrayList bajo presión podría llevar a las aplicaciones en un clúster a expandir sus arrays casi de forma sincronizada y, para tamaños de arrays grandes, podría conducir a la falta de capacidad de respuesta en la aplicación y a una interrupción, mientras está bajo presión, lo que es un comportamiento catastrófico.
Del mismo modo, se puede obtener un mejor rendimiento en una aplicación con el recolector de basura de rendimiento predeterminado, pero una vez que se obtienen aplicaciones java con heaps de 10 GB, se puede acabar bloqueando la aplicación durante 25 segundos durante una GC completa, lo que provoca tiempos de espera y fallos en las aplicaciones SOA y hace saltar por los aires los acuerdos de nivel de servicio si ocurre con demasiada frecuencia. Aunque el colector CMS requiere más recursos y no consigue el mismo rendimiento bruto, es una opción mucho mejor porque tiene una latencia más predecible y menor.
ArrayList es sólo una mejor opción para el rendimiento si todo lo que quieres decir con el rendimiento es el rendimiento y puedes ignorar la latencia. En mi experiencia en el trabajo no puedo ignorar la latencia en el peor de los casos.
Actualización (27 de agosto de 2021 -- 10 años después): Esta respuesta (mi respuesta más votada históricamente en SO también) es muy probablemente incorrecta (por las razones expuestas en los comentarios más abajo). Me gustaría añadir que ArrayList optimizará la lectura secuencial de la memoria y minimizará las pérdidas de líneas de caché y TLB, etc. La sobrecarga de copia cuando el Array crece más allá de los límites es probablemente intrascendente en comparación (y puede hacerse mediante operaciones eficientes de la CPU). Además, es probable que esta respuesta empeore con el tiempo, dadas las tendencias del hardware. Las únicas situaciones en las que una LinkedList podría tener sentido sería algo muy complicado en el que tuvieras miles de Listas, cualquiera de las cuales podría crecer hasta alcanzar el tamaño de GB, pero en el que no se pudiera hacer una buena estimación en el momento de la asignación de la Lista y establecerlas todas con el tamaño de GB haría explotar el montón. Y si encuentras un problema como ese, entonces realmente necesitas una reingeniería, sea cual sea tu solución (y no me gusta sugerir a la ligera la reingeniería de código antiguo porque yo mismo mantengo montones y montones de código antiguo, pero ese sería un muy buen caso en el que el diseño original simplemente se ha quedado sin recorrido y necesita ser desechado). No obstante, dejaré mi pobre opinión de hace décadas para que la leas. Simple, lógica y bastante equivocada.
¿No sería otra solución gestionar el tamaño de la lista programáticamente utilizando el método ensureCapacity() de ArrayList? Mi pregunta es ¿por qué se almacenan tantas cosas en un montón de estructuras de datos frágiles cuando podrían almacenarse mejor en un mecanismo de caché o db? El otro día tuve una entrevista en la que juraban por los males de ArrayList, pero vengo aquí y me parece que el análisis de la complejidad es mejor en todos los sentidos. GRAN PUNTO DE DISCUSIÓN, SIN EMBARGO. ¡GRACIAS!
una vez que tienes aplicaciones java con heaps de 10GB puedes acabar bloqueando la aplicación durante 25 segundos durante un Full GCs lo que provoca timeouts En realidad, con LinkedList se asesina al recolector de basura durante las GCs completas, ya que tiene que iterar la LinkedList demasiado grande con la pérdida de caché en cada nodo.
@bestsss Lo que dice es que nunca se desencadenará un ciclo completo de GC con listas de enlaces; la lista crecerá y se reducirá en incrementos de un elemento y la GC del CMS se ejecutará continuamente; sin contratiempos.
Sí, lo sé, esta es una pregunta antigua, pero aportaré mis dos centavos:
LinkedList es casi siempre la elección equivocada, en cuanto a rendimiento. Hay algunos algoritmos muy específicos en los que se requiere un LinkedList, pero son muy, muy raros y el algoritmo normalmente dependerá específicamente de la capacidad de LinkedList para insertar y eliminar elementos en el medio de la lista con relativa rapidez, una vez que se ha navegado hasta allí con un ListIterator.
Hay un caso de uso común en el que LinkedList supera a ArrayList: el de una cola. Sin embargo, si tu objetivo es el rendimiento, en lugar de LinkedList deberías considerar el uso de un ArrayBlockingQueue (si puedes determinar un límite superior en el tamaño de tu cola por adelantado, y puedes permitirte asignar toda la memoria por adelantado), o esto Implementación de CircularArrayList . (Sí, es de 2001, así que tendrás que generarlo, pero he obtenido ratios de rendimiento comparables a los citados en el artículo ahora mismo en una JVM reciente)
A partir de Java 6 se puede utilizar ArrayDeque . docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
ArrayDeque es más lento que LinkedList a menos que todas las operaciones estén en el mismo extremo. Está bien cuando se usa como pila, pero no es una buena cola.
No es cierto - al menos para la implementación de Oracle en jdk1.7.0_60 y en la siguiente prueba. He creado una prueba donde hago un bucle de 10 millones de veces y tengo un Deque de 10 millones de enteros al azar. Dentro del bucle sondeo un elemento de y ofrezco un elemento constante. En mi ordenador, LinkedList es más de 10 veces más lento que ArrayDeque y utiliza menos memoria). La razón es que, a diferencia de ArrayList, ArrayDeque mantiene un puntero a la cabeza del Array para no tener que mover todos los elementos cuando se elimina la cabeza.
Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.
7 votos
Véase también: Matriz frente a lista enlazada
7 votos
Basta con ver la cita del autor de LinkedList stackoverflow.com/a/42529652/2032701 y tendrás una idea práctica del asunto.