sirve - ¿Cuándo usar LinkedList sobre ArrayList en Java?




metodos linkedlist java (20)

Siempre he sido uno para usar simplemente:

List<String> names = new ArrayList<>();

Utilizo la interfaz como el nombre de tipo para la portabilidad , de modo que cuando hago preguntas como éstas puedo volver a trabajar mi código.

¿Cuándo se debe utilizar LinkedList sobre ArrayList y viceversa?

https://code.i-harness.com


1) Búsqueda: la operación de búsqueda de ArrayList es bastante rápida en comparación con la operación de búsqueda de LinkedList. get (int index) en ArrayList proporciona el rendimiento de O (1) mientras que el rendimiento de LinkedList es O (n).

Motivo: ArrayList mantiene un sistema basado en índices para sus elementos, ya que utiliza implícitamente la estructura de datos de la matriz, lo que lo hace más rápido para buscar un elemento en la lista. En el otro lado, LinkedList implementa una lista doblemente enlazada que requiere el recorrido a través de todos los elementos para buscar un elemento.

2) Eliminación: La operación de eliminación de LinkedList da un rendimiento O (1), mientras que ArrayList ofrece un rendimiento variable: O (n) en el peor de los casos (al eliminar el primer elemento) y O (1) en el mejor de los casos (Al eliminar el último elemento) .

Conclusión: la eliminación del elemento LinkedList es más rápida en comparación con ArrayList.

Motivo: cada uno de los elementos de LinkedList mantiene dos punteros (direcciones), que apuntan a los dos elementos vecinos en la lista. Por lo tanto, la eliminación solo requiere un cambio en la ubicación del puntero en los dos nodos vecinos (elementos) del nodo que se eliminará. Mientras que en ArrayList, todos los elementos deben cambiarse para completar el espacio creado por el elemento eliminado.

3) Rendimiento de inserciones: el método de adición LinkedList proporciona O (1) rendimiento, mientras que ArrayList proporciona O (n) en el peor de los casos. La razón es la misma que se explica para eliminar.

4) Sobrecarga de memoria: ArrayList mantiene índices y datos de elementos, mientras que LinkedList mantiene datos de elementos y dos punteros para nodos vecinos, por lo que el consumo de memoria es alto en LinkedList comparativamente.

Hay pocas similitudes entre estas clases que son las siguientes:

Tanto ArrayList como LinkedList son implementaciones de la interfaz de lista. Ambos mantienen el orden de inserción de los elementos, lo que significa que al mostrar los elementos ArrayList y LinkedList, el conjunto de resultados tendría el mismo orden en el que los elementos se insertaron en la Lista. Ambas clases no están sincronizadas y se pueden sincronizar explícitamente mediante el método Collections.synchronizedList. El iterador y el listIterator devueltos por estas clases son a prueba de fallas (si la lista se modifica estructuralmente en cualquier momento después de que se crea el iterador, de cualquier manera, excepto a través de los métodos de eliminación o adición propios del iterador, el iterador emitirá una excepción de modificación concurrente).

¿Cuándo usar LinkedList y cuándo usar ArrayList?

1) Como se explicó anteriormente, las operaciones de inserción y extracción dan un buen rendimiento (O (1)) en LinkedList en comparación con ArrayList (O (n)). Por lo tanto, si hay un requisito de adición y eliminación frecuentes en una aplicación, entonces LinkedList es la mejor opción.

2) Las operaciones de búsqueda (método de obtención) son rápidas en ArrayList (O (1)) pero no en LinkedList (O (n)) por lo que si hay menos operaciones de agregar y eliminar y más requisitos de operaciones de búsqueda, ArrayList sería su mejor apuesta.


Como alguien que ha estado haciendo ingeniería de rendimiento operacional en servicios web SOA a gran escala durante aproximadamente una década, preferiría el comportamiento de LinkedList sobre ArrayList. Si bien el rendimiento en estado estable de LinkedList es peor y, por lo tanto, podría llevar a comprar más hardware: el comportamiento de ArrayList bajo presión podría hacer que las aplicaciones de un clúster expandan sus arreglos casi en sincronicidad y, por lo tanto, una gran cantidad de arreglos podría generar una falta de respuesta en la aplicación y una interrupción, mientras que bajo presión, que es un comportamiento catastrófico.

Del mismo modo, puede obtener un mejor rendimiento en una aplicación del recolector de basura predeterminado, pero una vez que obtenga aplicaciones java con pilas de 10 GB, puede terminar bloqueando la aplicación durante 25 segundos durante un GC completo que causa tiempos de espera y fallos en las aplicaciones SOA. y sopla sus SLAs si ocurre demasiado a menudo. A pesar de que el recopilador de CMS toma más recursos y no logra el mismo rendimiento en bruto, es una opción mucho mejor porque tiene una latencia más previsible y más pequeña.

ArrayList es solo una mejor opción para el rendimiento si todo lo que quiere decir con rendimiento es rendimiento y puede ignorar la latencia. En mi experiencia en mi trabajo, no puedo ignorar la latencia más desfavorable.


Es una pregunta de eficiencia. LinkedList es rápido para agregar y eliminar elementos, pero tarda en acceder a un elemento específico. ArrayList es rápido para acceder a un elemento específico, pero puede demorarse en agregarse a cualquiera de los extremos y, especialmente, demorarse en eliminarse en el medio.

Array vs ArrayList vs LinkedList vs Vector va más en profundidad, al igual que Linked List .


Hasta ahora, parece que nadie se ha ocupado de la huella de memoria de cada una de estas listas, aparte del consenso general de que una lista LinkedList es "mucho más" que una lista de ArrayList por lo que hice algunos cálculos numéricos 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 las LinkedLists ArrayLists y ArrayLists de 32 y 64 bits.

Nota: los tamaños que se muestran para las líneas de ArrayList son para listas recortadas : en la práctica, la capacidad de la matriz de respaldo en un ArrayList es generalmente mayor que la cantidad actual de elementos.

Nota 2: (gracias a BeeOnRope) Como CompressedOops está predeterminado ahora desde mediados de JDK6 y superiores, los valores a continuación para máquinas de 64 bits básicamente coincidirán con sus equivalentes de 32 bits, a menos que, por supuesto, lo desactiven específicamente.

El resultado muestra claramente que LinkedList es mucho más que ArrayList , especialmente con un alto número de elementos. Si la memoria es un factor, manténgase alejado de las LinkedLists .

A continuación, las fórmulas que utilicé, avíseme si he hecho algo incorrecto y lo arreglaré. 'b' es 4 u 8 para sistemas de 32 o 64 bits, y 'n' es el número de elementos. Tenga en cuenta que la razón de los mods es que todos los objetos en java ocuparán un espacio de múltiplos de 8 bytes, independientemente de si se usan 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)

ArrayList es esencialmente una matriz. LinkedList se implementa como una lista de doble LinkedList .

El get es bastante claro. O (1) para ArrayList , porque ArrayList permite el acceso aleatorio mediante el uso de índice. O (n) para LinkedList , porque primero debe encontrar el índice. Nota: hay diferentes versiones de add y remove .

LinkedList es más rápido en agregar y quitar, pero más lento en obtener. En resumen, LinkedList debe ser preferido si:

  1. No hay gran cantidad de acceso aleatorio de elemento.
  2. Hay un gran número de operaciones de agregar / quitar

=== ArrayList ===

  • añadir (E e)
    • añadir al final de ArrayList
    • requiere el costo de cambio de tamaño de memoria.
    • O (n) peor, O (1) amortizado.
  • agregar (índice int, elemento E)
    • añadir a una posición de índice específica
    • requiere desplazamiento y posible costo de cambio de tamaño de memoria
    • En)
  • eliminar (índice int)
    • eliminar un elemento especificado
    • requiere desplazamiento y posible costo de cambio de tamaño de memoria
    • En)
  • eliminar (Objeto o)
    • eliminar la primera aparición del elemento especificado de esta lista
    • primero hay que buscar el elemento, y luego cambiar y cambiar el tamaño de la memoria.
    • En)

=== LinkedList ===

  • añadir (E e)

    • añadir al final de la lista
    • O (1)
  • agregar (índice int, elemento E)

    • inserte en la posición especificada
    • Necesito encontrar el puesto primero
    • En)
  • retirar()
    • eliminar el primer elemento de la lista
    • O (1)
  • eliminar (índice int)
    • eliminar elemento con índice especificado
    • Necesito encontrar el elemento primero
    • En)
  • eliminar (Objeto o)
    • Eliminar la primera aparición del elemento especificado.
    • Necesito encontrar el elemento primero
    • En)

Aquí hay una figura de programcreek.com ( add y remove son el primer tipo, es decir, agregar un elemento al final de la lista y eliminar el elemento en la posición especificada en la lista):


ArrayList es lo que quieres. LinkedList es casi siempre un error (de rendimiento).

¿Por qué LinkedList apesta:

  • Utiliza muchos objetos de memoria pequeños y, por lo tanto, afecta el rendimiento en todo el proceso.
  • Muchos objetos pequeños son malos para la localidad de caché.
  • Cualquier operación indexada requiere un recorrido transversal, es decir, tiene un rendimiento O (n). Esto no es obvio en el código fuente, lo que lleva a los algoritmos O (n) más lentos que si se usara ArrayList .
  • Conseguir un buen rendimiento es complicado.
  • Incluso cuando el rendimiento de big-O es el mismo que ArrayList , probablemente será mucho más lento de todos modos.
  • Es desconcertante ver a LinkedList en la fuente porque probablemente sea la elección equivocada.

ArrayListy LinkedListambos implementos List interfacey sus métodos y resultados son casi idénticos. Sin embargo, hay pocas diferencias entre ellas que hacen que una sea mejor que otra dependiendo del requisito.

ArrayList Vs LinkedList

1) la Search: ArrayListoperación de búsqueda es bastante rápida en comparación con la LinkedListoperación de búsqueda. get(int index)En ArrayListda el rendimiento de O(1)mientras que el LinkedListrendimiento es O(n).

Reason: ArrayListmantiene el sistema basado en índices para sus elementos, ya que utiliza implícitamente la estructura de datos de la matriz, lo que hace que sea más rápido para buscar un elemento en la lista. En el otro lado LinkedListimplementa una lista doblemente enlazada que requiere el recorrido a través de todos los elementos para buscar un elemento.

2) la Deletion: LinkedListoperación de eliminación da O(1)rendimiento mientras que ArrayListproporciona rendimiento variable: O(n)en el peor de los casos (al eliminar el primer elemento) y O(1)en el mejor de los casos (al eliminar el último elemento).

Conclusión: la eliminación del elemento LinkedList es más rápida en comparación con ArrayList.

Motivo: el elemento LinkedList mantiene dos punteros (direcciones) que apuntan a los dos elementos vecinos en la lista. Por lo tanto, la eliminación solo requiere un cambio en la ubicación del puntero en los dos nodos vecinos (elementos) del nodo que se va a eliminar. Mientras que en ArrayList, todos los elementos deben cambiarse para completar el espacio creado por el elemento eliminado.

3) Inserts Performance: LinkedListAñadir método da O(1)rendimiento mientras que ArrayListda O(n)en el peor de los casos. La razón es la misma que se explica para eliminar.

4) Memory Overhead: ArrayListmantiene índices y datos de elementos mientras LinkedListmantiene datos de elementos y dos punteros para nodos vecinos

por lo tanto el consumo de memoria es alto en LinkedList comparativamente.

Hay pocas similitudes entre estas clases que son las siguientes:

  • Tanto ArrayList como LinkedList son implementaciones de la interfaz de lista.
  • Ambos mantienen el orden de inserción de los elementos, lo que significa que al mostrar los elementos ArrayList y LinkedList, el conjunto de resultados tendría el mismo orden en el que los elementos se insertaron en la Lista.
  • Ambas clases no están sincronizadas y se pueden sincronizar explícitamente mediante el método Collections.synchronizedList.
  • Las iteratory listIteratordevueltas por estas clases son fail-fast(si la lista se modifica estructuralmente en cualquier momento después de que se crea el iterador, de cualquier forma, excepto a través de los iterator'smétodos propios de eliminación o adición, el iterador throwa ConcurrentModificationException).

¿Cuándo usar LinkedList y cuándo usar ArrayList?

  • Como se explicó anteriormente, las operaciones de inserción y extracción dan un buen rendimiento (O(1))en LinkedListcomparación con ArrayList(O(n)).

    Por lo tanto, si hay un requisito de adición y eliminación frecuentes en la aplicación, entonces LinkedList es la mejor opción.

  • Las get methodoperaciones de búsqueda ( ) son rápidas Arraylist (O(1))pero no enLinkedList (O(n))

    así que si hay menos operaciones de agregar y eliminar y más requisitos de operaciones de búsqueda, ArrayList sería su mejor apuesta.


1) Estructura de datos subyacente

La primera diferencia entre ArrayList y LinkedList viene con el hecho de que ArrayList está respaldado por Array, mientras que LinkedList está respaldado por LinkedList. Esto conducirá a más diferencias en el rendimiento.

2) LinkedList implementa Deque

Otra diferencia entre ArrayList y LinkedList es que, aparte de la interfaz de la Lista, LinkedList también implementa la interfaz de Deque, que proporciona las primeras operaciones de entrada y salida () y varias funciones de Deque. 3) Agregar elementos en ArrayList Agregar elementos en ArrayList es una operación O (1) si no activa el cambio de tamaño de Array, en cuyo caso se convierte en O (log (n)), por otro lado, agregar un elemento en LinkedList es una operación O (1), ya que no requiere ninguna navegación.

4) Eliminar un elemento de una posición

Para eliminar un elemento de un índice en particular, por ejemplo, llamando a remove (índice), ArrayList realiza una operación de copia que lo acerca a O (n), mientras que LinkedList debe atravesar ese punto que también lo hace O (n / 2) , ya que puede atravesar desde cualquier dirección en función de la proximidad.

5) Iterando sobre ArrayList o LinkedList

La iteración es la operación O (n) para LinkedList y ArrayList donde n es un número de un elemento.

6) Recuperar el elemento de una posición

La operación de obtención (índice) es O (1) en ArrayList, mientras que su O (n / 2) en LinkedList, ya que debe atravesar hasta esa entrada. Sin embargo, en Big O, la notación O (n / 2) es solo O (n) porque ignoramos las constantes allí.

7) memoria

LinkedList usa un objeto envoltorio, Entry, que es una clase anidada estática para almacenar datos y dos nodos a continuación y anteriores, mientras que ArrayList solo almacena datos en Array.

Por lo tanto, el requisito de memoria parece menor en el caso de ArrayList que en LinkedList, excepto en el caso en que Array realiza la operación de cambio de tamaño cuando copia contenido de un Array a otro.

Si Array es lo suficientemente grande, puede necesitar mucha memoria en ese punto y desencadenar la recolección de basura, lo que puede ralentizar el tiempo de respuesta.

De todas las diferencias anteriores entre ArrayList y LinkedList, parece que ArrayList es la mejor opción que LinkedList en casi todos los casos, excepto cuando realiza una operación add () frecuente que remove () o get ().

Es más fácil modificar una lista vinculada que ArrayList, especialmente si está agregando o eliminando elementos del inicio o el final, ya que la lista vinculada mantiene las referencias de esas posiciones internamente y se puede acceder a ellas en tiempo O (1).

En otras palabras, no necesita atravesar la lista enlazada para llegar a la posición donde desea agregar elementos, en ese caso, la adición se convierte en una operación O (n). Por ejemplo, insertar o eliminar un elemento en medio de una lista enlazada.

En mi opinión, use ArrayList sobre LinkedList para la mayoría de los propósitos prácticos en Java.


TL; DR debido a la arquitectura moderna de la computadora, ArrayListserá significativamente más eficiente para casi cualquier posible caso de uso y, por LinkedListlo tanto, debe evitarse excepto en casos muy singulares y extremos.

En teoría, LinkedList tiene un O (1) para el add(E element)

También agregar un elemento a la mitad de una lista debería ser muy eficiente.

La práctica es muy diferente, ya que LinkedList es una estructura de datos hostiles de caché . Desde el punto de vista del rendimiento: hay muy pocos casos en los que LinkedListpodría ser mejor que el Cache-friendly ArrayList .

Aquí están los resultados de una prueba de referencia que inserta elementos en ubicaciones aleatorias. Como puede ver, la lista de matrices es mucho más eficiente, aunque en teoría cada inserción en el medio de la lista requerirá "mover" los n elementos posteriores de la matriz (los valores más bajos son mejores):

Trabajando en un hardware de última generación (cachés más grandes y más eficientes), los resultados son aún más concluyentes:

LinkedList toma mucho más tiempo para lograr el mismo trabajo. source Código Fuente

Existen dos motivos principales para esto:

  1. Principalmente - que los nodos del LinkedListse dispersan aleatoriamente en la memoria. La RAM ("Memoria de acceso aleatorio") no es realmente aleatoria y los bloques de memoria se deben buscar en la memoria caché. Esta operación lleva tiempo, y cuando tales recuperaciones ocurren con frecuencia, las páginas de memoria en el caché deben reemplazarse todo el tiempo -> Fallos de caché -> El caché no es eficiente. ArrayListlos elementos se almacenan en la memoria continua, que es exactamente lo que la arquitectura moderna de la CPU está optimizando.

  2. Se LinkedList requiere un secundario para retener los punteros de retroceso / avance, lo que significa 3 veces el consumo de memoria por valor almacenado en comparación con ArrayList.

DynamicIntArray , por cierto, es una implementación de ArrayList personalizada Int(tipo primitivo) y no Objetos; por lo tanto, todos los datos se almacenan de manera adyacente, por lo tanto, aún más eficientes.

Un elemento clave a recordar es que el costo de obtener el bloque de memoria es más significativo que el costo de acceder a una sola celda de memoria. Es por eso que el lector de 1 MB de memoria secuencial es hasta 400 veces más rápido que leer esta cantidad de datos de diferentes bloques de memoria:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Fuente: Números de latencia que todo programador debe saber

Solo para aclarar aún más el punto, verifique el punto de referencia de agregar elementos al principio de la lista. Este es un caso de uso en el que, en teoría, LinkedListdeberían brillar realmente, y ArrayListdeberían presentar resultados pobres o incluso peores:

Nota: este es un punto de referencia de C ++ Std lib, pero mi experiencia anterior muestra que los resultados de C ++ y Java son muy similares. Código fuente

Copia de una mayor secuencial de la memoria es una operación optimizada por la CPU moderna - el cambio de la teoría y la realidad lo que, de nuevo, ArrayList/ Vectormucho más eficiente

Créditos: Todos los puntos de referencia publicados aquí son creados por Kjell Hedström . Incluso más datos se pueden encontrar en su blog.


ArrayList y LinkedList tienen sus propias ventajas y desventajas.

ArrayList usa una dirección de memoria contigua en comparación con LinkedList, que usa punteros hacia el siguiente nodo. Entonces, cuando desea buscar un elemento en un ArrayList es más rápido que hacer n iteraciones con LinkedList.

Por otro lado, la inserción y eliminación en una lista enlazada son mucho más fáciles porque solo tiene que cambiar los punteros, mientras que una lista de arrays implica el uso de la operación de cambio para cualquier inserción o eliminación.

Si tiene operaciones frecuentes de recuperación en su aplicación, use un ArrayList. Si tiene una inserción y eliminación frecuentes, use una lista enlazada.


Depende de qué operaciones harás más en la Lista.

ArrayListEs más rápido acceder a un valor indexado. Es mucho peor al insertar o eliminar objetos.

Para obtener más información, lea cualquier artículo que habla sobre la diferencia entre matrices y listas vinculadas.


He leído las respuestas, pero hay un escenario en el que siempre uso una lista enlazada sobre una lista de arreglos que quiero compartir para escuchar las opiniones:

Cada vez que tenía un método que devuelve una lista de datos obtenidos de una base de datos, siempre uso una lista enlazada.

Mi razonamiento fue que debido a que es imposible saber exactamente cuántos resultados estoy obteniendo, no se perderá la memoria (como en ArrayList la diferencia entre la capacidad y el número real de elementos), y no se perderá tiempo intentando duplicar la capacidad.

En cuanto a ArrayList, estoy de acuerdo en que al menos siempre debe usar el constructor con la capacidad inicial, para minimizar la duplicación de los arreglos lo más posible.


Además de los otros buenos argumentos anteriores, debe observar la interfaz de los ArrayListimplementos RandomAccess, mientras que los LinkedListimplementos Queue.

Entonces, de alguna manera, abordan problemas ligeramente diferentes, con diferencias de eficiencia y comportamiento (consulte su lista de métodos).


Aquí está la notación Big-O en ArrayListy LinkedListy también CopyOnWrite-ArrayList:

Lista de arreglo

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Lista enlazada

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Basándote en estos tienes que decidir qué elegir. :)


La operación get (i) en ArrayList es más rápida que LinkedList, porque:
ArrayList: Implementación de matriz de tamaño variable de la interfaz de lista
LinkedList: Implementación de lista de enlaces dobles de las interfaces de lista y Deque

Las operaciones que indizan en la lista recorrerán la lista desde el principio o el final, lo que esté más cerca del índice especificado.


Sé que este es un post antiguo, pero honestamente no puedo creer que nadie mencione los LinkedListimplementos Deque. Basta con mirar los métodos en Deque(y Queue); si quieres una comparación justa, intente ejecutar LinkedListen contra ArrayDequey hacer una comparación de características para la función.


Tanto remove () como insert () tienen una eficiencia de tiempo de ejecución de O (n) tanto para ArrayLists como para LinkedLists. Sin embargo, la razón detrás del tiempo de procesamiento lineal proviene de dos razones muy diferentes:

En una ArrayList, se llega al elemento en O (1), pero al eliminar o insertar algo, se convierte en O (n) porque es necesario cambiar todos los elementos siguientes.

En una lista enlazada, se necesita O (n) para llegar al elemento deseado, ya que tenemos que comenzar desde el principio hasta que alcancemos el índice deseado. En realidad, la eliminación o inserción es constante, porque solo tenemos que cambiar 1 referencia para remove () y 2 referencias para insert ().

Cuál de los dos es más rápido para insertar y quitar depende de dónde suceda. Si estamos más cerca del comienzo, LinkedList será más rápido, porque tenemos que pasar por relativamente pocos elementos. Si estamos más cerca del final, un ArrayList será más rápido, porque llegaremos en un tiempo constante y solo tendremos que cambiar los pocos elementos restantes que lo siguen. Cuando se realiza precisamente en el medio, el LinkedList será más rápido porque recorrer n elementos es más rápido que mover n valores.

Bonificación: Si bien no hay forma de hacer estos dos métodos O (1) para una ArrayList, en realidad hay una forma de hacerlo en las listas enlazadas. Digamos que queremos recorrer toda la Lista eliminando e insertando elementos en nuestro camino. Por lo general, comenzaría desde el principio para cada elemento con LinkedList, también podríamos "guardar" el elemento actual en el que estamos trabajando con un iterador. Con la ayuda del iterador, obtenemos una eficiencia de O (1) para eliminar () e insertar () cuando se trabaja en una lista vinculada. Por lo que es el único beneficio de rendimiento que conozco donde un LinkedList siempre es mejor que un ArrayList.


Una característica importante de una lista vinculada (que no leí en otra respuesta) es la concatenación de dos listas. Con una matriz, esto es O (n) (+ sobrecarga de algunas reasignaciones) con una lista enlazada, esto es solo O (1) o O (2) ;-)

Importante : para Java LinkedListesto no es cierto! Consulte ¿Existe un método rápido de concat para la lista enlazada en Java?


Una lista de matrices es esencialmente una matriz con métodos para agregar elementos, etc. (y debería usar una lista genérica en su lugar). Es una colección de elementos a los que se puede acceder a través de un indexador (por ejemplo, [0]). Implica una progresión de un elemento a otro.

Una lista enlazada especifica una progresión de un elemento al siguiente (Elemento a -> elemento b). Puede obtener el mismo efecto con una lista de arreglos, pero una lista enlazada dice absolutamente qué elemento debe seguir al anterior.








linked-list