Lista enlazada en Java

La lista enlazada es parte del marco de la colección presente en el paquete java.util . Esta clase es una implementación de la estructura de datos LinkedList, que es una estructura de datos lineal donde los elementos no se almacenan en ubicaciones contiguas y cada elemento es un objeto separado con una parte de datos y una parte de dirección. Los elementos se vinculan mediante punteros y direcciones. Cada elemento se conoce como un Node. Debido a la dinámica y facilidad de las inserciones y eliminaciones, son preferibles a los arreglos. También tiene algunas desventajas, como que no se puede acceder directamente a los Nodes, sino que debemos comenzar desde la cabeza y seguir el enlace para llegar al Node al que deseamos acceder.

¿Cómo funciona LinkedList internamente?

Dado que LinkedList actúa como una array dinámica y no tenemos que especificar el tamaño al crearla, el tamaño de la lista aumenta automáticamente cuando agregamos y eliminamos elementos dinámicamente. Y además, los elementos no se almacenan de forma continua. Por lo tanto, no hay necesidad de aumentar el tamaño. Internamente, LinkedList se implementa utilizando la estructura de datos de lista doblemente enlazada . La principal diferencia entre una lista enlazada normal y una lista doblemente enlazada es que una lista doblemente enlazada contiene un puntero adicional, normalmente llamado puntero anterior, junto con el puntero siguiente y los datos que están en la lista enlazada individualmente. 
 

Constructores en la LinkedList

Para crear una LinkedList, necesitamos crear un objeto de la clase LinkedList. La clase LinkedList consta de varios constructores que permiten la posible creación de la lista. Los siguientes son los constructores disponibles en esta clase:
 

1. LinkedList(): este constructor se utiliza para crear una lista enlazada vacía. Si deseamos crear una LinkedList vacía con el nombre ll, entonces, se puede crear como: 

LinkedList ll = new LinkedList();  

2. LinkedList (Colección C): este constructor se usa para crear una lista ordenada que contiene todos los elementos de una colección específica, tal como los devuelve el iterador de la colección. Si deseamos crear una LinkedList con el nombre ll, entonces, se puede crear como: 

LinkedList ll = new LinkedList(C);

Métodos para Java LinkedList

Ejemplo:

// Java Program to Demonstrate
// Implementation of LinkedList
// class
  
// Importing required classes
import java.util.*;
  
// Main class
public class GFG {
  
    // Main driver method
    public static void main(String args[])
    {
        // Creating object of the
        // class linked list
        LinkedList<String> ll = new LinkedList<String>();
  
        // Adding elements to the linked list
        ll.add("A");
        ll.add("B");
        ll.addLast("C");
        ll.addFirst("D");
        ll.add(2, "E");
  
        System.out.println(ll);
  
        ll.remove("B");
        ll.remove(3);
        ll.removeFirst();
        ll.removeLast();
  
        System.out.println(ll);
    }
}

[D, A, E, B, C]
[A]

En la ilustración anterior, AbstractList , CopyOnWriteArrayList y AbstractSequentialList son las clases que implementan la interfaz de lista. Se implementa una funcionalidad separada en cada una de las clases mencionadas. Están:

1. AbstractList: esta clase se usa para implementar una lista no modificable, para lo cual solo se necesita extender esta clase AbstractList e implementar solo los métodos get() y size().
2. CopyOnWriteArrayList: esta clase implementa la interfaz de lista. Es una versión mejorada de ArrayList en la que todas las modificaciones (agregar, establecer, eliminar, etc.) se implementan al hacer una copia nueva de la lista.

Realización de varias operaciones en LinkedList

1. Agregar elementos
2. Actualización de elementos
3. Quitar elementos
4. Iterando sobre elementos

Veamos cómo realizar algunas operaciones básicas en LinkedList para entenderlo mejor de la siguiente manera:

Operación 1: Adición de elementos

Para agregar un elemento a un ArrayList, podemos usar el método add() . Este método está sobrecargado para realizar múltiples operaciones basadas en diferentes parámetros. Están:  

• add(Object): este método se usa para agregar un elemento al final de LinkedList.
• add(int index, Object): este método se usa para agregar un elemento en un índice específico en LinkedList.

Ejemplo:

// Java program to add elements 
// to a LinkedList
    
import java.util.*; 
    
public class GFG { 
    
    public static void main(String args[]) 
    { 
        LinkedList<String> ll = new LinkedList<>(); 
    
        ll.add("Geeks"); 
        ll.add("Geeks"); 
        ll.add(1, "For"); 
    
        System.out.println(ll); 
    } 
}

[Geeks, For, Geeks]

Operación 2: Elementos cambiantes

Después de agregar los elementos, si deseamos cambiar el elemento, se puede hacer usando el método set() . Dado que una LinkedList está indexada, el elemento que deseamos cambiar está referenciado por el índice del elemento. Por lo tanto, este método toma un índice y el elemento actualizado que debe insertarse en ese índice.

Ejemplo:

// Java program to change elements 
// in a LinkedList 
    
import java.util.*; 
    
public class GFG { 
    
    public static void main(String args[]) 
    { 
        LinkedList<String> ll = new LinkedList<>(); 
    
        ll.add("Geeks"); 
        ll.add("Geeks"); 
        ll.add(1, "Geeks"); 
    
        System.out.println("Initial LinkedList " + ll); 
    
        ll.set(1, "For"); 
    
        System.out.println("Updated LinkedList " + ll); 
    } 
} 

Initial LinkedList [Geeks, Geeks, Geeks]
Updated LinkedList [Geeks, For, Geeks]

Operación 3: Eliminación de elementos

Para eliminar un elemento de una LinkedList, podemos usar el método remove() . Este método está sobrecargado para realizar múltiples operaciones basadas en diferentes parámetros. Están: 

• remove(Object): este método se usa simplemente para eliminar un objeto de LinkedList. Si hay varios de estos objetos, se elimina la primera aparición del objeto.
• remove(int index): dado que una LinkedList está indexada, este método toma un valor entero que simplemente elimina el elemento presente en ese índice específico en la LinkedList. Después de eliminar el elemento y los índices de los elementos se actualizan, el objeto de LinkedList se actualiza dando una nueva lista después de la eliminación de los elementos.

Ejemplo:

// Java program to remove elements 
// in a LinkedList
    
import java.util.*; 
    
public class GFG { 
    
    public static void main(String args[]) 
    { 
        LinkedList<String> ll = new LinkedList<>(); 
    
        ll.add("Geeks"); 
        ll.add("Geeks"); 
        ll.add(1, "For"); 
    
        System.out.println( 
            "Initial LinkedList " + ll); 
    
        ll.remove(1); 
    
        System.out.println( 
            "After the Index Removal " + ll); 
    
        ll.remove("Geeks"); 
    
        System.out.println( 
            "After the Object Removal " + ll); 
    } 
} 

Initial LinkedList [Geeks, For, Geeks]
After the Index Removal [Geeks, Geeks]
After the Object Removal [Geeks]

Operación 4: iteración de LinkedList

Hay varias formas de iterar a través de LinkedList. Las formas más famosas son usar el bucle for básico en combinación con un método get() para obtener el elemento en un índice específico y el bucle for avanzado.

Ejemplo:

// Java program to iterate the elements 
// in an LinkedList
    
import java.util.*; 
    
public class GFG { 
    
    public static void main(String args[]) 
    { 
        LinkedList<String> ll 
            = new LinkedList<>(); 
    
        ll.add("Geeks"); 
        ll.add("Geeks"); 
        ll.add(1, "For"); 
    
        // Using the Get method and the 
        // for loop 
        for (int i = 0; i < ll.size(); i++) { 
    
            System.out.print(ll.get(i) + " "); 
        } 
    
        System.out.println(); 
    
        // Using the for each loop 
        for (String str : ll) 
            System.out.print(str + " "); 
    } 
} 

Geeks For Geeks 
Geeks For Geeks