Lista enlazada en Java

¡Hola! Todas las conferencias recientes se han dedicado al estudio de la lista ArrayList . Esta estructura de datos es muy conveniente y le permite resolver muchos problemas. Sin embargo, Java tiene muchas otras estructuras de datos. ¿Por qué? En primer lugar, porque la gama de tareas existentes es muy amplia y, para diferentes tareas, las estructuras de datos diferentes son más efectivas . Hoy nos familiarizaremos con una nueva estructura: una lista doblemente enlazada LinkedList . Averigüemos cómo funciona, por qué se llama doblemente conectado y en qué se diferencia de ArrayList . En una LinkedList, los elementos son en realidad eslabones de una cadena. Cada elemento, además de los datos que almacena, tiene un enlace al elemento anterior y siguiente . Estos enlaces le permiten pasar de un elemento a otro. Se crea así:

public class Main {

   public static void main(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 Moscow");

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

       System.out.println(earlBio);

   }
}

Conclusión:

[Hello World! My name is Earl, I love Java, I live in Moscow]

Así es como se verá la estructura de nuestra lista: Veamos cómo se agrega un nuevo elemento. Esto se hace usando el add().

earlBio.add(str2);

En el momento de esta línea de código, nuestra lista consta de un elemento: la cadena str1. Veamos qué sucede a continuación en la imagen: Como resultado str2, str1se conectan a través de los enlaces almacenados en ellos nexty previous: Ahora debes comprender la idea principal de una lista doblemente enlazada. Los elementos LinkedListson una lista única precisamente gracias a esta cadena de eslabones. No hay ninguna matriz dentro LinkedList, como en ArrayList, ni nada similar. Todo el trabajo con ArrayList (en general) se reduce a trabajar con la matriz interna. Todo el trabajo LinkedListse reduce a cambiar enlaces. Esto se ve muy claramente agregando un elemento en el medio de la lista:

public class Main {

   public static void main(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 Moscow");

       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 sobrecargado add()le permite especificar un índice específico para el nuevo elemento. En este caso, queremos agregar una línea str2entre str1y str3. Esto es lo que sucederá dentro: Y como resultado de cambiar los enlaces internos, el elemento str2se agrega exitosamente a la lista: Ahora los 3 elementos están vinculados. Desde el primer elemento de la cadena nextpuedes ir al último y regresar. Hemos descubierto más o menos la inserción, pero ¿qué pasa con la eliminación de elementos? El principio de funcionamiento es el mismo. Simplemente redefinimos los vínculos de los dos elementos “a los lados” del que se está eliminando:

public class Main {

   public static void main(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 Moscow");

       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 sucederá si eliminamos el elemento con índice 1 (está en el medio de la lista): después de redefinir los enlaces, obtenemos el resultado deseado: a diferencia de la eliminación, ArrayListno hay cambios de elementos de la matriz y similares. Simplemente redefinimos las referencias de los elementos str1y str3. Ahora se señalan entre sí y el objeto str2ha “salido” de esta cadena de eslabones y ya no forma parte de la lista.

Resumen de métodos

Tiene LinkedListmuchas similitudes con ArrayListlos métodos. Por ejemplo, métodos como add(), remove(), indexOf(), clear(), contains()(es el elemento contenido en la lista), set()(insertar un elemento con reemplazo) size()están presentes en ambas clases. Aunque (como descubrimos en el ejemplo add()y remove()) muchos de ellos funcionan de manera diferente internamente, en última instancia hacen lo mismo. Sin embargo, LinkedListtiene métodos separados para trabajar con el principio y el final de la lista, que no están presentes en ArrayList:

• addFirst(), addLast(): 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 + '\'' +
               '}';
   }
}

Conclusión:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]
[Car{model='Ford Mondeo'}, Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}, Car{model='Fiat Ducato'}]

Como resultado, Ford terminó en lo más alto de la lista y Fiat al final.

• peekFirst(), peekLast(): devuelve el primer/último elemento de la lista. Devuelve nullsi 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());
}

Conclusión:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}

• pollFirst(), pollLast(): devuelve el primer/último elemento de la lista y lo elimina de la lista . Regresar nullsi 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("¿Qué queda en la lista?");
   System.out.println(cars);
}

Conclusión:

Car{model='Ferrari 360 Spider'}
Car{model='Lamborghini Diablo'}
Qué осталось в списке?
[Car{model='Bugatti Veyron'}]

• toArray(): devuelve una matriz de 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));
}

Conclusión:

[Car{model='Ferrari 360 Spider'}, Car{model='Bugatti Veyron'}, Car{model='Lamborghini Diablo'}]

Ahora sabemos cómo funciona LinkedListy en qué se diferencia ArrayList. ¿ Cuáles son los beneficios de usarlo LinkedList? En primer lugar, trabajando con la mitad de la lista . Insertar y eliminar en el medio LinkedListes mucho más sencillo que en ArrayList. Simplemente redefinimos los vínculos de los elementos vecinos y el elemento innecesario "cae" de la cadena de vínculos. Mientras que en ArrayListnosotros:

• compruebe si hay suficiente espacio (al insertar)
• si no es suficiente, cree una nueva matriz y copie los datos allí (al pegar)
• eliminar/insertar un elemento y desplazar todos los demás elementos hacia la derecha/izquierda (dependiendo del tipo de operación). Además, la complejidad de este proceso depende en gran medida del tamaño de la lista. Una cosa es copiar/mover 10 elementos, pero otra muy distinta es hacer lo mismo con un millón de elementos.

Es decir, si en su programa las operaciones de inserción/eliminación ocurren con más frecuencia en el medio de la lista, LinkedListdeberí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("Tiempo de ejecución de LinkedList (en milisegundos) = " + (System.currentTimeMillis()-start));
   }
}

Conclusión:

Время работы для LinkedList (в мoсекундах) = 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("Tiempo de ejecución de ArrayList (en milisegundos) = " + (System.currentTimeMillis()-start));
   }
}

Conclusión:

Время работы для ArrayList (в миллисекундах) = 181

¡De repente! Parecería que estábamos realizando una operación que LinkedListdebería haber sido mucho más eficiente: insertar 100 elementos en el medio de la lista. Y nuestra lista es enorme: 5.000.000 de elementos: ¡ ArrayListteníamos que desplazar un par de millones de elementos cada vez que los insertábamos! ¿A qué se debe su victoria? Primero, se accede a un elemento en ArrayListun período de tiempo fijo. Cuando usted indica:

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

entonces en el caso de ArrayList[2_000_000] esta es una dirección específica en la memoria, porque tiene una matriz dentro. Mientras que la LinkedListmatriz no. Buscará el elemento número 2_000_000 a lo largo de la cadena de eslabones. Para él, esta no es una dirección en la memoria, sino un enlace al que aún hay que llegar:

fistElement.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next………

Como resultado, con cada inserción (eliminación) en el medio de la lista, ArrayListya sabe la dirección exacta en la memoria a la que debe acceder, pero LinkedListaún necesita "descubrir" el lugar correcto. En segundo lugar , la cuestión está en la estructura de ArrayList'a' misma. La expansión de la matriz interna, la copia de todos los elementos y el desplazamiento de elementos se realiza mediante una función interna especial: System.arrayCopy(). Funciona muy rápido porque está especialmente optimizado para este trabajo. Pero en situaciones en las que no es necesario "pisar fuerte" hasta alcanzar el índice deseado, LinkedListrealmente se muestra mejor. Por ejemplo, si la inserción se produce 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) {
       //escribe tu codigo aqui
       Date currentTime = new Date();
       insert1000000(list);
       Date newTime = new Date();
       long msDelay = newTime.getTime() - currentTime.getTime(); //calcular la diferencia
       System.out.println("Resultado en milisegundos: " + msDelay);
       return msDelay;

   }

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

}

Conclusión:

Результат в миллисекундах: 43448
Результат в миллисекундах: 107

¡Un resultado completamente diferente! ¡Se necesitaron más de 43 segundos para insertar un millón de elementos al principio de la lista ArrayList, mientras que LinkedListse completó en 0,1 segundos! Precisamente el hecho de que en esta situación LinkedListno teníamos que “correr” cada vez a través de la cadena de eslabones hasta el centro de la lista. Inmediatamente encontró el índice requerido al principio de la lista, y allí la diferencia en los principios operativos ya estaba de su lado :) De hecho, la discusión " ArrayListversus LinkedList" está muy extendida y no profundizaremos en ella por el momento. nivel. Lo principal que debes recordar:

• No todas las ventajas de una colección en particular "en papel" funcionarán en la realidad (lo vimos usando el ejemplo del medio de la lista)
• No hay que irse a los extremos a la hora de elegir una colección (“ ArrayListsiempre es más rápido, úsala y no te equivocarás. LinkedListHace tiempo que nadie la usa”).

Aunque incluso el creador LinkedListJoshua Bloch lo dice :) Sin embargo, este punto de vista está lejos de ser 100% correcto y estamos convencidos de ello. En nuestro ejemplo anterior LinkedListfuncionó 400 (!) veces más rápido. Otra cosa es que hay muy pocas situaciones en las que LinkedListsería la mejor opción. Pero existen y, en el momento adecuado, LinkedListpueden ayudarte seriamente. No olvide lo que hablamos al comienzo de la conferencia: diferentes estructuras de datos son más efectivas para diferentes tareas. Es imposible decir con un 100% de confianza qué estructura de datos será mejor hasta que se conozcan todas las condiciones del problema. Más adelante sabrás más sobre estas colecciones y te resultará más fácil elegir. Pero la opción más sencilla y eficaz es siempre la misma: probar ambas con datos reales de tu programa. Entonces podrás ver con tus propios ojos los resultados de ambas listas y definitivamente no te equivocarás :)