1. Historia deLinkedList

Java tiene otra clase de colección Java heredada del lenguaje C++. Esta es la LinkedListclase que implementa una "lista enlazada".

Exteriormente, a LinkedListparece ser lo mismo que un ArrayList. La LinkedListclase tiene todos los mismos métodos que la ArrayListclase. En principio, siempre puedes usar a LinkedListen lugar de an ArrayListy todo funcionará.

Entonces, ¿por qué necesitamos otra clase de lista?

La respuesta tiene todo que ver con la estructura interna de la LinkedListclase. En lugar de una matriz, utiliza una lista doblemente enlazada . Explicaremos qué es eso un poco más adelante.

La LinkedListestructura interna diferente de la clase hace que sea más rápido insertar elementos en el medio de la lista.

En Internet, a menudo puede encontrar comparaciones de las clases ArrayListy LinkedList:

Operación Método Lista de arreglo Lista enlazada
Añadir un elemento
add(value)
Rápido Muy rapido
Insertar un elemento
add(index, value)
Lento Muy rapido
obtener un elemento
get(index)
Muy rapido Lento
Establecer un elemento
set(index, value)
Muy rapido Lento
Quitar un elemento
remove(index)
Lento Muy rapido

Todo parece lo suficientemente claro: si necesita insertar elementos en la lista con frecuencia, use LinkedList; si rara vez, entonces use ArrayList. Pero la realidad es un poco diferente.


2. Nadie usaLinkedList

Nadie usa LinkedList.

Incluso el autor de la LinkedListclase tuiteó recientemente: "¿Alguien realmente lo usa LinkedList? Lo escribí y nunca lo uso".

Entonces, ¿cuál es el trato?

Primero, la ArrayListclase comenzó a poder insertar elementos en el medio de la lista muy rápidamente. Al insertar un elemento en el medio de la lista, debe desplazar todos los elementos después del punto de inserción en 1 hacia el final de la lista. Esto solía tomar tiempo.

Pero ahora todo ha cambiado. Todos los elementos de una matriz están cerca unos de otros en el mismo bloque de memoria, por lo que la operación para desplazar los elementos se realiza mediante un comando muy rápido de bajo nivel: .System.arraycopy()

Además, los procesadores de hoy en día tienen una memoria caché grande que normalmente puede contener toda la matriz, lo que permite que los elementos de la matriz se desplacen dentro de la memoria caché en lugar de en la memoria. Un millón de elementos se desplazan fácilmente en un solo milisegundo.

En segundo lugar, la LinkedListclase puede insertar elementos rápidamente si los inserta mediante un iterador. Si usa un iterador para pasar por un LinkedListe insertar constantemente nuevos elementos (o eliminar los existentes), la operación es súper rápida.

Si simplemente agrega elementos a un LinkedListobjeto dentro de un bucle, cada operación de inserción rápida se acompaña de una operación lenta de "obtención de elemento".

La realidad es mucho más cercana a esto:

Operación Método Lista de arreglo Lista enlazada
Añadir un elemento
add(value)
Rápido Muy rapido
Insertar un elemento
add(index, value)
Lento Muy lento
obtener un elemento
get(index)
Muy rapido Muy lento
Establecer un elemento
set(index, value)
Muy rapido Muy lento
Quitar un elemento
remove(index)
Lento Muy lento
Insertar usando un iterador
it.add(value)
Lento Muy rapido
Quitar usando un iterador
it.remove()
Lento Muy rapido

¿ Por qué obtener un elemento de una LinkedListoperación tan lenta?

Puede responder esa pregunta después de familiarizarse un poco con cómo LinkedListestá estructurado.


3. Cómo LinkedListestá estructurado

LinkedListtiene una estructura interna diferente a ArrayList. No tiene una matriz interna para almacenar elementos. En su lugar, utiliza una estructura de datos llamada lista doblemente entintada .

Cada elemento de una lista doblemente enlazada almacena una referencia al elemento anterior y al elemento siguiente. Esto es algo así como una línea en una tienda, donde cada persona recuerda a la persona que está frente a ellos así como a la persona que está detrás de ellos.

Así es como se ve una lista de este tipo en la memoria:

Cómo se estructura LinkedList

La cabeza y la cola (celdas con fondo gris) son las variables firsty last, que almacenan referencias a Nodeobjetos.

En el medio, tienes una cadena de Nodeobjetos (objetos, no variables). Cada uno de ellos consta de tres campos:

  • prev— almacena una referencia (enlace) al Nodeobjeto anterior (celdas con fondo amarillo).
  • value— almacena el valor de este elemento de la lista (celdas con fondo verde).
  • next— almacena una referencia (enlace) al siguiente Nodeobjeto (celdas con fondo azul)

El segundo objeto (dirección F24) es el siguiente ( next) del primer objeto y el anterior ( prev) del tercero. El campo amarillo del tercer objeto contiene la dirección F24 y el campo azul del primer objeto contiene la dirección F24.

Las flechas del primer y tercer objeto apuntan al mismo segundo objeto. Entonces sería más correcto dibujar las flechas así.

Cómo se estructura LinkedList 2



4. Insertar un elemento en una lista enlazada

Para agregar a alguien a una línea como esta, solo necesita obtener el permiso de dos personas paradas una al lado de la otra. La primera persona recuerda al recién llegado como "la persona que está detrás de mí", y la segunda persona los recuerda como "la persona que está delante de mí".

Todo lo que necesita hacer es cambiar las referencias de los dos objetos vecinos:

Insertar un elemento en una lista enlazada

Agregamos un nuevo elemento a nuestra lista cambiando las referencias del segundo y tercer objeto. El nuevo objeto es el siguiente para el antiguo segundo objeto y el anterior para el antiguo tercer objeto. Y, por supuesto, el nuevo objeto en sí necesita almacenar las referencias correctas: su objeto anterior es el segundo objeto anterior y su siguiente objeto es el tercer objeto anterior.

Eliminar un elemento es aún más fácil: si queremos eliminar, digamos, el objeto número 100 de la lista, solo tenemos que cambiar el campo del objeto 99 nextpara que apunte al objeto 101 y cambiar el prevcampo por el 101. objeto para que apunte al 99. Eso es todo.

Pero conseguir el objeto número 100 no es tan fácil.


5. Eliminar un elemento de una lista

Para obtener el elemento número 100 de una lista vinculada, debe:

Obtenga el primer objeto: lo hace usando la firstvariable en el LinkedListobjeto. El nextcampo del primer objeto almacena una referencia al segundo objeto. Así es como obtenemos el segundo objeto. El segundo objeto tiene una referencia al tercero, y así sucesivamente.

Si necesitamos obtener una referencia al objeto número 100, debemos movernos secuencialmente a través de todos los objetos del 1 al 100. Y si necesitamos el millonésimo elemento en una lista, ¡necesitamos iterar más de un millón de objetos uno tras otro!

Y si estos objetos se agregaron a la lista en diferentes momentos, estarán ubicados en diferentes partes de la memoria y es poco probable que terminen en el caché del procesador al mismo tiempo. Esto significa que iterar sobre los elementos de una lista enlazada no solo es lento, sino muy lento.

Eso es con lo que estamos lidiando.

Entonces, ¿por qué te estamos enseñando cómo LinkedListfunciona esta lentitud?

Bueno, durante las entrevistas de trabajo se le preguntará en qué LinkedListse diferencia deArrayList . Definitivamente.