LinkedList En Java: Implementación, Funcionamiento y Ejemplos

En programación, una lista enlazada es una estructura de datos que consta de un conjunto de nodos, donde cada nodo contiene un valor y una referencia al siguiente nodo en la lista. En Java, la clase LinkedList proporciona una implementación de una lista enlazada, lo que permite a los programadores crear y manipular listas enlazadas de manera eficiente.

En este artículo, exploraremos en detalle la implementación, el funcionamiento y los ejemplos de LinkedList en Java.

¿Qué es una lista enlazada?

Antes de profundizar en la implementación de LinkedList en Java, es importante entender qué es una lista enlazada.

Una lista enlazada es una estructura de datos en la que cada elemento se almacena en un nodo que contiene tanto el valor del elemento como una referencia al siguiente nodo en la lista. La primera y última posición de la lista se conocen como la cabeza y la cola, respectivamente.

La principal ventaja de las listas enlazadas es que permiten la inserción y eliminación eficiente de elementos en cualquier posición de la lista, lo que las hace ideales para aplicaciones que requieren la modificación frecuente de elementos.

Implementación de LinkedList en Java

En Java, la clase LinkedList se implementa en el paquete java.util. Para utilizar LinkedList en Java, es necesario importar la clase LinkedList al comienzo del archivo Java.

import java.util.LinkedList;

Creación de una lista enlazada

Para crear una nueva LinkedList en Java, se puede utilizar el constructor LinkedList sin argumentos:

Añadir y eliminar elementos de una lista enlazada

Para añadir elementos a una LinkedList, se puede utilizar el método add:

Para eliminar elementos de una LinkedList, se puede utilizar el método remove:

Acceder a elementos de una lista enlazada

Para acceder a un elemento de una LinkedList, se puede utilizar el método get:

Recorrer una lista enlazada

Para recorrer una LinkedList en Java, se puede utilizar un bucle for-each:

Ejemplos de LinkedList en Java

Ejemplo 1: Crear una lista enlazada de enteros y agregar elementos

Ejemplo 2: Crear una lista enlazada de cadenas y eliminar elementos

Similar a las matrices en Java, LinkedList es una estructura de datos lineal. Sin embargo, los elementos de LinkedList no se almacenan en lugares contiguos como las matrices, sino que se enlazan entre sí mediante punteros. Cada elemento de la LinkedList tiene la referencia (dirección/puntero) al siguiente elemento de la LinkedList.

Ejemplo 2: Crear una lista enlazada de cadenas y eliminar elementos

En este ejemplo, creamos una lista enlazada de cadenas y eliminamos el elemento «Elemento 2» de la lista utilizando el método remove. Luego, recorremos la lista e imprimimos los elementos restantes.

Representación de LinkedList

Cada elemento de la Lista de Enlaces se llama Nodo. Cada Nodo de la ListaEnlazada contiene dos elementos: 1) Contenido del elemento 2) Puntero/Dirección/Referencia al siguiente Nodo de la LinkedList.

Así es como se ve una LinkedList:

Nota:
1. La cabecera de la LinkedList sólo contiene la dirección del primer elemento de la lista.
2. El Último elemento de la ListaEnlazada contiene nulo en la parte del puntero del nodo porque es el final de la Lista, por lo que no apunta a nada como se muestra en el diagrama anterior.
3. El diagrama que se muestra arriba representa una lista vinculada individualmente. Hay otra variación de tipo complejo de LinkedList que se llama lista doblemente enlazada, el nodo de una lista doblemente enlazada contiene tres partes: 1) Puntero al nodo anterior de la lista enlazada 2) contenido del elemento 3) puntero al siguiente nodo de la lista enlazada.

¿Por qué necesitamos una lista vinculada?

Usted debe ser consciente de las matrices, que es también una estructura de datos lineales, pero las matrices tienen ciertas limitaciones, tales como:
1) El tamaño de la matriz es fijo, lo cual se decide cuando creamos una matriz, por lo que es difícil predecir el número de elementos por adelantado, si el tamaño declarado se queda corto entonces no podemos aumentar el tamaño de una matriz y si declaramos una matriz de gran tamaño y no necesitamos almacenar tantos elementos entonces es un desperdicio de memoria.

2) Los elementos de la matriz necesitan ubicaciones de memoria contiguas para almacenar sus valores.

3) Insertar un elemento en un array es caro en términos de rendimiento ya que tenemos que desplazar varios elementos para hacer un espacio para el nuevo elemento. Por ejemplo:
Digamos que tenemos una matriz que tiene los siguientes elementos: 10, 12, 15, 20, 4, 5, 100, ahora si queremos insertar un nuevo elemento 99 después del elemento que tiene el valor 12 entonces tenemos que desplazar todos los elementos después de 12 a su derecha para hacer espacio para el nuevo elemento.

Del mismo modo, la eliminación de un elemento de la matriz es también una operación costosa desde el punto de vista del rendimiento porque todos los elementos después del elemento eliminado tienen que desplazarse a la izquierda.

Estas limitaciones se manejan en la Lista de Enlaces proporcionando las siguientes características:

1. La lista de enlaces permite la asignación dinámica de memoria, lo que significa que la asignación de memoria se hace en el momento de la ejecución por el compilador y no es necesario mencionar el tamaño de la lista durante la declaración de la lista de enlaces.

2. Los elementos de la lista vinculada no necesitan ub icaciones de memoria contiguas porque los elementos se vinculan entre sí utilizando la parte de referencia del nodo que contiene la dirección del siguiente nodo de la lista.

3. 3. Las operaciones de inserción y eliminación en la lista enlazada no son costosas en términos de rendimiento porque la adición y eliminación de un elemento de la lista enlazada no requiere el desplazamiento del elemento, sólo el puntero del nodo anterior y siguiente requiere el cambio.

Jerarquía de la clase LinkedList en Java

Ejemplo de Java Linked List para añadir elementos

En el siguiente ejemplo estamos usando los métodos add(), addFirst() y addLast() para añadir los elementos en los lugares deseados de la LinkedList, hay varios de estos métodos útiles en la clase LinkedList que he mencionado al final de este artículo.

import java.util.LinkedList;

public class EjemploLinkedList {

public static void main(String[] args) {

// Creamos una Linked List
LinkedList<String> linkedList = new LinkedList<>();

// Agregamos elementos a la Linked List
linkedList.add(«Elemento 1»);
linkedList.add(«Elemento 2»);
linkedList.add(«Elemento 3»);

// Imprimimos la Linked List
System.out.println(«Contenido de la Linked List: » + linkedList);

// Agregamos un elemento al inicio de la Linked List
linkedList.addFirst(«Elemento 0»);

// Agregamos un elemento al final de la Linked List
linkedList.addLast(«Elemento 4»);

// Imprimimos la Linked List después de agregar elementos
System.out.println(«Contenido de la Linked List después de agregar elementos: » + linkedList);
}
}

Este código crea una Linked List vacía y luego agrega elementos a ella usando el método add(). Luego agrega un elemento al principio de la Linked List usando addFirst() y agrega otro elemento al final de la Linked List usando addLast(). Finalmente, el contenido de la Linked List se imprime usando System.out.println().

Salida:

Ejemplo en Java de la eliminación de elementos de la LinkedList

En el siguiente ejemplo estamos comprobando los pocos métodos de eliminación populares en la LinkedList que se utilizan para eliminar elementos de ciertas posiciones en la LinkedList. La explicación detallada de estos métodos, junto con los ejemplos, se tratan en los tutoriales separados, los enlaces se proporcionan al final de este artículo.

import java.util.LinkedList;

public class EjemploLinkedList {

public static void main(String[] args) {

// Creamos una Linked List
LinkedList<String> linkedList = new LinkedList<>();

// Agregamos elementos a la Linked List
linkedList.add(«Elemento 1»);
linkedList.add(«Elemento 2»);
linkedList.add(«Elemento 3»);

// Imprimimos la Linked List
System.out.println(«Contenido de la Linked List: » + linkedList);

// Eliminamos el primer elemento de la Linked List
linkedList.removeFirst();

// Eliminamos el último elemento de la Linked List
linkedList.removeLast();

// Eliminamos un elemento en particular de la Linked List
linkedList.remove(«Elemento 2»);

// Imprimimos la Linked List después de eliminar elementos
System.out.println(«Contenido de la Linked List después de eliminar elementos: » + linkedList);
}
}

Este código crea una Linked List con tres elementos y luego usa los métodos removeFirst(), removeLast() y remove() para eliminar elementos de la Linked List. Finalmente, el contenido actualizado de la Linked List se imprime usando System.out.println().

Salida:

Ejemplo de LinkedList en Java

import java.util.LinkedList;

public class EjemploLinkedList {

public static void main(String[] args) {

// Creamos una Linked List
LinkedList linkedList = new LinkedList<>();

// Agregamos elementos a la Linked List
linkedList.add(«Elemento 1»);
linkedList.add(«Elemento 2»);
linkedList.add(«Elemento 3»);

// Imprimimos la Linked List
System.out.println(«Contenido de la Linked List: » + linkedList);

// Accedemos al primer y último elemento de la Linked List
String primerElemento = linkedList.getFirst();
String ultimoElemento = linkedList.getLast();

// Imprimimos el primer y último elemento de la Linked List
System.out.println(«Primer elemento de la Linked List: » + primerElemento);
System.out.println(«Último elemento de la Linked List: » + ultimoElemento);

// Accedemos a un elemento específico de la Linked List
String tercerElemento = linkedList.get(2);

// Imprimimos el tercer elemento de la Linked List
System.out.println(«Tercer elemento de la Linked List: » + tercerElemento);
}
}
Este código crea una Linked List vacía y luego agrega elementos a ella usando el método add(). Luego, accede al primer y último elemento de la Linked List usando getFirst() y getLast(). Después, accede a un elemento específico de la Linked List usando get(). Finalmente, imprime los elementos de la Linked List usando System.out.println().

Métodos de la clase LinkedList:

Para todos los ejemplos de los métodos siguientes, considere llistobj como una referencia para LinkedList.

LinkedListllistobj = new Link edList();

1) add(Object item) booleano: Añade el ítem al final de la lista.

llistobj.add("Hola");

Añade la cadena «Hello» al final de la lista enlazada.

2) añadir el vacío (índice de int, elemento de objeto): Añade un elemento en el índice dado de la lista.

llistobj.add(2, "bye");

Añade la cadena «bye» en la 3ª posición (el índice 2 es la 3ª posición, ya que el índice comienza con 0).

3) addAll(Colección c) booleana: Añade todos los elementos de la colección c especificada a la lista. Lanza NullPointerException si la colección especificada es nula. Considere el siguiente ejemplo –

LinkedList<String> llistobj = new LinkedList<String>();ArrayList<String> arraylist= new ArrayList<String>();arraylist.add("String1");arraylist.add("String2");llistobj.addAll(arraylist);

Este trozo de código añadiría todos los elementos de ArrayList a la LinkedList.

4) addAll(int index , Collection c) booleano: Añade todos los elementos de la colección c a la lista a partir de un índice dado en la lista. Lanza NullPointerException si la colección c es nula y IndexOutOfBoundsException cuando el índice especificado está fuera del rango.

llistobj.add(5, arraylist);

Añadiría todos los elementos de la ArrayList a la LinkedList a partir de la posición 6 (índice 5).

5) void addFirst(Elemento de objeto): Añade el ítem (o elemento) en la primera posición de la lista.

llistobj.addFirst("texto");

Añade la cadena «texto» al principio de la lista.

6) anular addLast(Objeto ítem): Inserta el elemento especificado al final de la lista.

llistobj.addLast("Chaitanya");

Esta declaración añadirá una cadena «Chaitanya» al final de la lista enlazada.

7) void clear(): Elimina todos los elementos de una lista.

llistobj.clear();

8) objeto clone(): Devuelve la copia de la lista.

Por ejemplo, mi lista de enlaces tiene cuatro elementos: text1, text2, text3 y text4.

Objeto str= llistobj.clone(); System.out.println(str);

Salida: La salida del código anterior sería:

[texto1, texto2, texto3, texto4]

9) booleano contiene(Objeto artículo): Comprueba si el elemento dado está presente en la lista o no. Si el elemento está presente, entonces devuelve verdadero o falso.

boolean var = llistobj.contains("TestString");

Comprobará si la cadena «TestString» existe en la lista o no.

10) Objeto get(int index): Devuelve el elemento del índice especificado de la lista.

Objeto var = llistobj.get(2);

Recuperará el 3er ítem de la lista.

11) Objeto getFirst(): Recupera el primer elemento de la lista.

Objeto var = llistobj.getFirst();

12) Objeto getLast(): Se obtiene el último elemento de la lista.

Objeto var= llistobj.getLast();

13) int indexOf(Objeto item): Devuelve el índice del elemento especificado.

llistobj.indexOf("bye");

14) int lastIndexOf(Objeto item): Devuelve el índice de la última ocurrencia del elemento especificado.

int pos = llistobj.lastIndexOf("hola");

La variable entera pos tendrá el índice de la última ocurrencia de la cadena «hola».

15) Encuesta de objetos: Devuelve y elimina el primer elemento de la lista.

Objeto o = llistobj.poll();

16) Objeto pollFirst(): igual que el método poll(). Elimina el primer elemento de la lista.

Objeto o = llistobj.pollFirst();

17) Encuesta sobre el objeto Último: Devuelve y elimina el último elemento de la lista.

Objeto o = llistobj.pollLast();

18) Objeto remove(): Elimina el primer elemento de la lista.

llistobj.remove();

19) Eliminación de objetos (índice de inteligencia): Elimina el elemento de la lista que está presente en el índice especificado.

llistobj.remove(4);

Eliminará el quinto elemento de la lista.

20) Objeto remove(Objeto obj): Elimina el objeto especificado de la lista.

llistobj.remove("Objeto de prueba");

21) Objeto removidoFirst(): Elimina el primer elemento de la lista.

llistobj.removeFirst();

22) Objeto removeLast(): Elimina el último elemento de la lista.

llistobj.removeLast();

23) Objeto eliminarPrimeraOcurrencia(Objeto artículo): Elimina la primera ocurrencia del elemento especificado.

llistobj.removeFirstOccurrence("texto");

Eliminará la primera aparición de la cadena «text» de la lista.

24) Objeto removeLastOccurrence(Elemento de objeto): Elimina la última ocurrencia del elemento dado.

llistobj.removeLastOccurrence("String1);

Eliminará la última ocurrencia de la cadena «String1».

25) Conjunto de objetos (índice int, Elemento de objeto): Actualiza el elemento del índice especificado con el valor dado.

llistobj.set(2, "Test");

Actualizará el 3er elemento con la cadena «Test».

26) int size(): Devuelve el número de elementos de la lista.

llistobj.size();