Estructura de datos de lista enlazada en Java

Se crean diferentes estructuras de datos para diferentes propósitos. Es posible que conozca ArrayList (si aún no lo sabe, le recomendamos que lea sobre él primero). En este artículo, aprenderemos sobre LinkedList y nos daremos cuenta de para qué sirve esta colección. Si observa el código fuente de la clase LinkedList Java 8 (o una versión posterior del idioma) (en el sitio web de Oracle o en su IDE, en el caso de IDEA: crtl+B en el nombre de la clase), verá la siguiente declaración:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

Por el momento, la información más importante del código es el hecho de que LinkedList implementa las interfaces List y Deque . La interfaz de Lista mantiene la secuencia de adición de elementos y permite el acceso al elemento por índice. La cola "ordinaria" admite agregar elementos al final y extraerlos desde el principio. Deque es una cola bidireccional y admite agregar y eliminar elementos de ambos lados. Puede pensar en ello como una combinación de pila y cola. Entonces, LinkedList es una implementación de estos dos, y nos permite crear una cola bidireccional que consta de cualquier objeto, incluido nulo. Lista enlazadaes una colección de elementos. Lo podemos ver en el código fuente de la clase, esta vez presta atención a los campos:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Cada elemento, generalmente lo llamamos Nodo , contiene un objeto y referencias a dos objetos vecinos: el anterior y el siguiente. Por lo tanto, no es muy efectivo en términos de uso de la memoria. Como LinkedList en realidad es una estructura bidireccional, podemos agregar o eliminar fácilmente elementos de ambos lados.

Constructores de listas enlazadas

Volviendo al código fuente, podemos descubrir que LinkedList tiene dos constructores

• LinkedList() sin parámetros se usa para construir una lista vacía.
• >LinkedList(Collection<? extends E> c) es para crear una lista que contiene los elementos de la colección especificada, en orden, son devueltos por el iterador de la colección.

Declaración LinkedList

De hecho, una lista enlazada (Java o en cualquier otro lenguaje) consta de una secuencia de nodos. Cada nodo está diseñado para almacenar un objeto de un tipo definido al crear. Entonces, para crear LinkedList , el código Java es el siguiente:

LinkedList<Integer> myList = new LinkedList<>();

Tenemos un objeto para mantener una secuencia de enteros y enlaces a los vecinos. Sin embargo, está vacío en este momento.

Operaciones principales de LinkedList

Como de costumbre, en el caso de las colecciones, puede colocar elementos en LinkedList (al final o en el medio), eliminarlos de allí y obtener un elemento por índice. Así que aquí están:

• add(E elemento) Agrega el elemento especificado al final de esta lista;
• add(int index, elemento E) Inserta el elemento en la posición especificada index ;
• get(int index) Devuelve el elemento en la posición especificada en esta lista;
• remove(int index) Elimina el elemento que está en la posición index;
• remove(Object o) Elimina la primera aparición de ? o elemento de esta lista si está allí.
• remove() Recupera y elimina el primer elemento de la lista.

Implementación de listas enlazadas en Java, agregando y eliminando elementos. Ejemplo

Probemos estas operaciones en la práctica. Primero, la implementación de Java LinkedList: creando una LinkedList of Strings, agregando allí 3 elementos. Luego quite uno, luego agregue uno en el medio.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

El resultado de ejecutar este programa:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

Una LinkedList es parte del marco de la colección , puede usar Iterator para eliminar elementos, así como un iterador especial para listas: ListIterator . Aún más, las operaciones con iterador brindan los principales beneficios de la clase LinkedList : buen rendimiento de las operaciones de inserción/eliminación. Usando Iterator puede obtener un tiempo constante para ellos. Más adelante en este artículo, escribiremos un código de ejemplo para comparar ArrayList y LinkedList+Iterator

• Iterator.remove() elimina el último elemento devuelto por este iterador.
• ListIterator.add (elemento E) inserta un elemento en la lista

Ejemplo de Java LinkedList: cómo funciona Iterator

Aquí tenemos un pequeño código de ejemplo de Java LinkedList , donde intentamos agregar y eliminar a través de Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

El resultado de ejecutar este programa:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Más operaciones Java LinkedList :

• addFirst() , addLast() agrega un elemento al principio/final de una lista
• clear() elimina todos los elementos de la lista
• contiene (Objeto o) devuelve verdadero si la lista contiene el elemento o.
• indexOf(Object o) devuelve el índice de la primera aparición del elemento o, o -1 si no está en la lista.
• set (índice int, elemento E) reemplaza el elemento en la posición de índice con el elemento
• size() Devuelve la cantidad de elementos de la lista.
• toArray() devuelve una matriz que contiene todos los elementos de la lista desde el primero hasta el último elemento.

Por cierto, al ser una cola de dos tamaños, LinkedList en Java tiene operaciones específicas de pila:

• pop() que extrae un elemento de la pila (representado por la lista)
• push(E e) que empuja un elemento a la pila (representado por esta lista)

Cómo invertir LinkedList: ejemplo

Aquí hay un pequeño ejemplo, una tarea popular pero fácil para principiantes. Tenemos una LinkedList y deberíamos revertirla. El algoritmo más fácil es pasar por LinkedList en orden inverso y colocar cada elemento en el nuevo. Sin embargo, ¿quizás encuentres una mejor manera? Aquí está el código del programa Java de lista de enlaces inversos:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

El resultado:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: cuándo usar el primero

Tanto LinkedList como ArrayList son implementaciones de la interfaz List . LinkedList lo implementa con una lista doblemente enlazada. ArrayList lo implementa usando una matriz de cambio de tamaño dinámico. Como ya sabes, cada nodo de LinkedList contiene Objetos y dos referencias a los vecinos. Eso significa costos de memoria adicionales para almacenar referencias entre elementos en el caso de Java LinkedList . ArrayList lo implementa con una matriz de cambio de tamaño dinámico. Algunas operaciones de LinkedList y ArrayList tienen el mismo aspecto, pero funcionan de forma diferente. en la lista de arregloscaso, manipula con matrices internas, en LinkedList , con referencias. ArrayList es la implementación de listas más popular . Definitivamente debería usar ArrayList cuando el acceso al índice es una prioridad, ya que estas operaciones se realizan en tiempo constante. Agregar al final de la lista en promedio también se realiza en tiempo constante. Aún más, ArrayList no tiene costos adicionales por almacenar un montón de elementos. Puede contar como Desventajas la velocidad de las operaciones de inserción y eliminación cuando no se hace al final de la lista. Lista enlazadaes más útil en el caso del rendimiento de las operaciones de inserción y eliminación de alguna manera: si usa iteradores, ocurre en tiempo constante. Las operaciones de acceso por índice se realizan buscando desde el principio hasta el final (el que esté más cerca) del elemento deseado. Sin embargo, no olvide los costos adicionales por almacenar referencias entre elementos. Así que aquí las operaciones estándar de LinkedList y ArrayList con tiempos de ejecución algorítmicos. N se refiere a la cantidad de elementos que ya están en la lista. O(N) significa que en el peor de los casos deberíamos “recorrer” toda la lista hasta encontrar la posición necesaria, por ejemplo, para insertar el nuevo elemento en la lista. O(1)significa que la operación ocurre en tiempo constante, independientemente del número de elementos.

Complejidad de tiempo de LinkedList

Complejidad de tiempo de ArrayList

Cuándo usar LinkedList: ejemplo

Definitivamente, ArrayList es la implementación de Lista más popular . Sin embargo, puede encontrar situaciones en las que las operaciones de agregar o quitar se necesiten con demasiada frecuencia. En ese caso, LinkedList junto con Iterator podría ser beneficioso. Aquí hay un ejemplo. Tenemos una lista larga y debemos eliminar todos los elementos de esta lista. Hagamos esta tarea con ArrayList y LinkedList + Iterator . Comparamos el tiempo de cada operación y lo imprimimos en la consola. Aquí el código:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Resultado para ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Resultado para LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Como puede ver, en este caso, LinkedList es mucho más efectivo. Seamos honestos. En el desarrollo de software real, el uso de LinkedList es un tipo de evento raro. Sin embargo, un profesional debe conocer la existencia de esta estructura de datos y sus ventajas. Si en código real LinkedList es un invitado raro, en las entrevistas de Java Junior es muy popular. Y, sin embargo, esto es lo que escribió Joshua Bloch sobre LinkedList :

Complemento: Lista de enlaces individuales Java

No existe una lista de enlaces únicos entre las colecciones clásicas en Java, la lista de enlaces únicos es una estructura en la que cada nodo contiene un objeto y una referencia al siguiente nodo, pero no al anterior. Java LinkedList tiene dos enlaces, pero nadie interfiere con usted para crear su propia estructura de datos, como una sola, código>Lista enlazada. Aquí hay algunos pasos para resolver estas tareas:

1. Cree una clase de Nodo con dos atributos, datos y siguiente. Siguiente es una referencia al siguiente nodo.
2. Cree la clase FirstLast con dos atributos, cabeza y cola.
3. Cree un método add() para agregar un nuevo nodo a la lista. Compruebe si la lista está vacía primero ( head == null ). Si es así, cabeza y cola se refieren al nuevo nodo. Si la lista no está vacía, el nuevo nodo se agregará al final, por lo que el siguiente atributo de la cola se refiere al nodo agregado y el nuevo nodo se convierte en la cola de la lista.

Por cierto, también puede intentar crear su propia LinkedList como ejercicio. Buena suerte en tu aprendizaje.