Java LinkedList

¡Hola! Todas las lecciones más recientes se han dedicado a ArrayList . Esta estructura de datos es muy conveniente y útil. Puede manejar muchas tareas. Pero Java tiene muchas otras estructuras de datos. ¿Por qué? Sobre todo, porque la gama de tareas es enorme y las estructuras de datos más eficientes son diferentes para tareas diferentes. Hoy conoceremos una nueva estructura: Java LinkedList , una lista doblemente enlazada. Veamos cómo está organizado, por qué se llama doblemente enlazado, en qué se diferencia de ArrayList . Los elementos en una LinkedList de Java son en realidad enlaces en una sola cadena. Además de los datos, cada elemento almacena referencias a los elementos anterior y siguiente. Estas referencias le permiten pasar de un elemento a otro. Así es como se crea uno:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str2);
       earlBio.add(str3);
       earlBio.add(str4);

       System.out.println(earlBio);

   }
}

Salida: [¡Hola mundo! Mi nombre es Earl, me encanta Java, vivo en Canadá] Así es como se ve nuestra lista: Veamos cómo agregar un nuevo elemento. Esto se hace usando el método add() .

earlBio.add(str2);

En este punto del código, nuestra lista consta de un elemento: el String str1 . Veamos qué sucede a continuación en la imagen: Como resultado, str2 y str1 se vinculan a través de los vínculos siguiente y anterior almacenados en estos nodos de la lista: Ahora debe comprender la idea principal de una lista doblemente vinculada. Esta cadena de enlaces es precisamente lo que hace que los elementos LinkedList sean una sola lista. A diferencia de ArrayList , LinkedList no tiene una matriz ni nada parecido a una matriz en su interior. Cualquier trabajo (bueno, la mayoría) con ArrayList se reduce a trabajar con la matriz interna. Cualquier trabajo con Java LinkedListse reduce a cambiar los enlaces. Esto se puede ver muy claramente agregando un elemento en el medio de la lista:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       System.out.println(earlBio);

   }
}

Como puede ver, el método add() sobrecargado le permite especificar un índice específico para un elemento nuevo. En este caso, queremos agregar String str2 entre str1 y str3 . Esto es lo que sucederá internamente: después de cambiar los enlaces internos, str2 se agregó con éxito a la lista: ahora los 3 elementos están conectados. Puede moverse a través del siguiente enlace desde el primer elemento de la cadena hasta el último y viceversa. Entonces, nos sentimos bastante cómodos con la inserción, pero ¿qué pasa con la eliminación de elementos? El principio es exactamente el mismo. Simplemente actualizamos los enlaces en los dos elementos "a la izquierda y a la derecha" del elemento que se está eliminando:

public class Main {

   public static void main(java.lang.String[] args) {

       String str1 = new String("Hello World!");
       String str2 = new String("My name is Earl");
       String str3 = new String("I love Java");
       String str4 = new String("I live in Canada");

       LinkedList<String> earlBio = new LinkedList<>();
       earlBio.add(str1);
       earlBio.add(str3);
       earlBio.add(1, str2);

       earlBio.remove(1);
       System.out.println(earlBio);
   }
}

Esto es lo que sucede si eliminamos el elemento con el índice 1 (está en el medio de la lista): Después de actualizar los enlaces, obtenemos el resultado deseado: A diferencia de la operación de eliminación en ArrayList , aquí no es necesario cambiar los elementos de la matriz o hacer cualquier cosa por el estilo. Solo actualizamos los enlaces para str1 y str3 . Ahora se apuntan entre sí, y str2 se ha " abandonado " de la cadena de enlaces y ya no forma parte de la lista.

Descripción general de los métodos

LinkedList tiene muchos métodos en común con ArrayList . Por ejemplo, ambas clases tienen métodos como add() , remove() , indexOf() , clear() , contains() (indica si un elemento está en la lista), set() (reemplaza un elemento existente) y tamaño() . Aunque muchos de ellos funcionan de manera diferente internamente (como encontramos con add() y remove() ), el resultado final es el mismo. Sin embargo, LinkedList tiene métodos separados para trabajar con el principio y el final de la lista, que ArrayList no tiene:

• addFirst() , addLast() : estos métodos para agregar un elemento al principio/final de la lista

public class Car {

   String model;

   public Car(String model) {
       this.model = model;
   }

   public static void main(String[] args) {
       LinkedList<Car> cars = new LinkedList<>();
       Car ferrari = new Car("Ferrari 360 Spider");
       Car bugatti = new Car("Bugatti Veyron");
       Car lambo = new Car("Lamborghini Diablo");
       Car ford = new Car("Ford Mondeo");
       Car fiat = new Car("Fiat Ducato");

       cars.add(ferrari);
       cars.add(bugatti);
       cars.add(lambo);
       System.out.println(cars);

       cars.addFirst(ford);
       cars.addLast(fiat);
       System.out.println(cars);
   }

   @Override
   public String toString() {
       return "Car{" +
               "model='" + model + '\'' +
               '}';
   }
}

Salida: [Coche{modelo='Ferrari 360 Spider'}, Coche{modelo='Bugatti Veyron'}, Coche{modelo='Lamborghini Diablo'}] [Coche{modelo='Ford Mondeo'}, Coche{modelo=' Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}] Terminamos con "Ford" en la parte superior de la lista, y "Fiat" al final.

• peekFirst() , peekLast() : los métodos devuelven el primer/último elemento de la lista. Devuelven nulo si la lista está vacía.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.peekFirst());
   System.out.println(cars.peekLast());
}

Resultado: Coche{modelo='Ferrari 360 Spider'} Coche{modelo='Lamborghini Diablo'}

• pollFirst() , pollLast() : estos métodos devuelven el primer/último elemento de la lista y lo eliminan de la lista. Devuelven nulo si la lista está vacía.

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   System.out.println(cars.pollFirst());
   System.out.println(cars.pollLast());

   System.out.println ("What's on the list?");
   System.out.println(cars);
}

Resultado: Coche{modelo='Ferrari 360 Spider'} Coche{modelo='Lamborghini Diablo'} ¿Qué queda en la lista? [Coche{modelo='Bugatti Veyron'}]

• toArray() : este método devuelve una matriz que contiene los elementos de la lista

public static void main(String[] args) {
   LinkedList<Car> cars = new LinkedList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");

   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
   Car[] carsArray = cars.toArray(new Car[3]);
   System.out.println(Arrays.toString(carsArray));
}

Salida: [Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}] Ahora sabemos cómo funciona LinkedList y en qué se diferencia su organización de ArrayList . ¿ Cuáles son los beneficios de usar LinkedList ? Sobre todo, nos beneficiamos cuando trabajamos en el medio de la lista. Las operaciones de inserción y eliminación en medio de una LinkedList son mucho más sencillas que en una ArrayList . Simplemente actualizamos los enlaces de los elementos vecinos, y el elemento no deseado "cae" de la cadena de enlaces. Pero en un ArrayList , debemos

• comprobar si hay suficiente espacio (al insertar)
• si no, creamos una nueva matriz y copiamos los datos allí (al insertar)
• quitamos/insertamos el elemento, y movemos todos los demás elementos a la derecha/izquierda (dependiendo del tipo de operación). Y la complejidad de este proceso depende en gran medida del tamaño de la lista. Una cosa es copiar/mover 10 elementos y otra muy distinta hacer lo mismo con un millón de elementos.

En otras palabras, si las operaciones de inserción/eliminación en el medio de la lista son las más comunes en su programa, LinkedList debería ser más rápido que ArrayList .

En teoria

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new LinkedList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by LinkedList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Salida: Tiempo tomado por LinkedList (en milisegundos) = 1873

public class Main {

   public static void main(String[] args) {
       List<Integer> list = new ArrayList<>();

       for (int i = 0; i < 5_000_000; i++) {
           list.add(new Integer(i));
       }

       long start = System.currentTimeMillis();

       for (int i = 0; i < 100; i++) {
           list.add(2_000_000, new Integer(Integer.MAX_VALUE));
       }
       System.out.println("Time taken by ArrayList (in milliseconds) = " + (System.currentTimeMillis()-start));
   }
}

Salida: Tiempo tomado por ArrayList (en milisegundos) = 181 ¡ Eso fue inesperado! Realizamos una operación en la que LinkedList debería ser mucho más eficiente: insertar 100 elementos en medio de una lista. Y nuestra lista es enorme: 5.000.000 de elementos. ¡ ArrayList tuvo que cambiar un par de millones de elementos con cada inserción! ¿Cómo ganó? Primero, el tiempo requerido para que ArrayList acceda a los elementos es fijo (constante). Cuando escribes

list.add(2_000_000, new Integer(Integer.MAX_VALUE));

entonces ArrayList [2_000_000] es una dirección de memoria específica (después de todo, la lista tiene una matriz interna). Pero, LinkedList no tiene una matriz. Buscará el elemento número 2_000_000 a lo largo de la cadena de eslabones. Para LinkedList, no se trata de una dirección de memoria, sino de un enlace al que aún se debe acceder: fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next. siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.siguiente.... Como resultado, durante cada inserción (eliminación) en el medio de la lista , ArrayList ya conoce la dirección de memoria exacta para acceder, pero LinkedList aún necesita "llegar allí". En segundo lugar, está la estructura de ArrayList.sí mismo. Una función interna especial ( System.arrayCopy() ) expande la matriz interna y copia y desplaza todos los elementos. Es muy rápido, porque está optimizado para este trabajo específico. Pero cuando no tiene que "llegar" a un índice en particular, LinkedList es el ganador. Supongamos que insertamos al principio de la lista. Intentemos insertar un millón de elementos allí:

public class Main {

   public static void main(String[] args) {
       getTimeMsOfInsert(new ArrayList());
       getTimeMsOfInsert(new LinkedList());
   }

   public static long getTimeMsOfInsert(List list) {
       // Write your code here
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); // Calculate the difference
       System.out.println("The result in milliseconds: " + msDelay);
       return msDelay;

   }

   public static void insert1000000(List list) {
       for (int i = 0; i < 1000000; i++) {
           list.add(0, new Object());
       }
   }

}

Salida: El resultado en milisegundos: 43448 El resultado en milisegundos: 107 ¡ Ahora obtenemos un resultado completamente diferente! ArrayList dedicó más de 43 segundos a insertar un millón de elementos al principio de la lista, mientras que LinkedList logró hacerlo en 0,1 segundos. LinkedList se benefició aquí, porque no tenía que pasar por la cadena de enlaces hasta el medio de la lista cada vez. Inmediatamente encuentra el índice necesario al principio de la lista, por lo que el algoritmo diferente ya es una ventaja. :) De hecho, la discusión " ArrayList versus LinkedList " está muy extendida, y no profundizaremos en ella en el nivel actual. Lo principal que debes recordar es esto:

• No todas las ventajas teóricas de una colección en particular siempre funcionan en la realidad (vimos esto con el ejemplo que involucra el medio de la lista)
• No adoptes una posición extrema a la hora de elegir una colección (" ArrayList siempre es más rápido. Úsalo y no te equivocarás. Nadie usa LinkedList desde hace mucho tiempo").

Aunque incluso el autor de LinkedList , Joshua Bloch, dice que este es el caso. :) Aún así, esta perspectiva está lejos de ser 100% correcta, y nos hemos convencido de ello. En nuestro ejemplo anterior, LinkedList fue 400 (!) veces más rápido. Otra cosa es que realmente hay pocas situaciones en las que LinkedList es la mejor opción. Pero existen, y en el momento adecuado LinkedListpuede recompensarte generosamente. No olvide lo que dijimos al comienzo de la lección: las estructuras de datos más eficientes son diferentes para diferentes tareas. Es imposible estar 100% seguro de qué estructura de datos será la mejor hasta que conozca todas las condiciones de su tarea. Sabrás más sobre estas colecciones más adelante, lo que te facilitará la elección. Pero la opción más simple y efectiva es siempre la misma: pruebe ambas con los datos reales utilizados en su programa. Entonces podrá ver por sí mismo cómo funcionan ambos tipos de listas y definitivamente no se equivocará. :) Para reforzar lo que aprendió, le sugerimos que vea una lección en video de nuestro Curso de Java