1. Historia deLinkedList
Java tiene otra clase de colección Java heredada del lenguaje C++. Esta es la LinkedList
clase que implementa una "lista enlazada".
Exteriormente, a LinkedList
parece ser lo mismo que un ArrayList
. La LinkedList
clase tiene todos los mismos métodos que la ArrayList
clase. En principio, siempre puedes usar a LinkedList
en lugar de an ArrayList
y todo funcionará.
Entonces, ¿por qué necesitamos otra clase de lista?
La respuesta tiene todo que ver con la estructura interna de la LinkedList
clase. En lugar de una matriz, utiliza una lista doblemente enlazada . Explicaremos qué es eso un poco más adelante.
La LinkedList
estructura 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 ArrayList
y LinkedList
:
Operación | Método | Lista de arreglo | Lista enlazada |
---|---|---|---|
Añadir un elemento |
|
Rápido | Muy rapido |
Insertar un elemento |
|
Lento | Muy rapido |
obtener un elemento |
|
Muy rapido | Lento |
Establecer un elemento |
|
Muy rapido | Lento |
Quitar un elemento |
|
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 LinkedList
clase tuiteó recientemente: "¿Alguien realmente lo usa LinkedList
? Lo escribí y nunca lo uso".
Entonces, ¿cuál es el trato?
Primero, la ArrayList
clase 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 LinkedList
clase puede insertar elementos rápidamente si los inserta mediante un iterador. Si usa un iterador para pasar por un LinkedList
e insertar constantemente nuevos elementos (o eliminar los existentes), la operación es súper rápida.
Si simplemente agrega elementos a un LinkedList
objeto 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 |
|
Rápido | Muy rapido |
Insertar un elemento |
|
Lento | Muy lento |
obtener un elemento |
|
Muy rapido | Muy lento |
Establecer un elemento |
|
Muy rapido | Muy lento |
Quitar un elemento |
|
Lento | Muy lento |
Insertar usando un iterador |
|
Lento | Muy rapido |
Quitar usando un iterador |
|
Lento | Muy rapido |
¿ Por qué obtener un elemento de una LinkedList
operación tan lenta?
Puede responder esa pregunta después de familiarizarse un poco con cómo LinkedList
está estructurado.
3. Cómo LinkedList
está estructurado
LinkedList
tiene 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:
La cabeza y la cola (celdas con fondo gris) son las variables first
y last
, que almacenan referencias a Node
objetos.
En el medio, tienes una cadena de Node
objetos (objetos, no variables). Cada uno de ellos consta de tres campos:
prev
— almacena una referencia (enlace) alNode
objeto 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 siguienteNode
objeto (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í.
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:
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 next
para que apunte al objeto 101 y cambiar el prev
campo 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 first
variable en el LinkedList
objeto. El next
campo 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 LinkedList
funciona esta lentitud?
Bueno, durante las entrevistas de trabajo se le preguntará en qué LinkedList
se diferencia deArrayList
. Definitivamente.
GO TO FULL VERSION