Aprende Implementación de LinkedList en Java

Desliza para mostrar el menú

Es momento de ponerte a prueba con algunas tareas realmente complejas.

Implementaremos nuestra estructura de datos simplificada—específicamente, la SinglyLinkedList.

Comencemos implementando la clase Node, que almacenará un valor y una referencia al siguiente Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

La implementación de la clase Node en SinglyLinkedList ya se demostró en el capítulo anterior, por lo que no nos detendremos mucho en ello.

A continuación, vamos a crear la clase SinglyLinkedList, donde definiremos toda la lógica para nuestra estructura de datos:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Creamos el campo Node head, que almacenará el primer elemento de nuestra estructura de datos.

En una LinkedList convencional, también existen un head y un tail que almacenan el primer y el último elemento de la estructura de datos. Dado que la estructura de datos debe estar vacía durante la inicialización, establecemos este campo en null en el constructor.

Nuestra estructura de datos debe soportar todas las operaciones CRUD.

Crear

Ahora, avancemos paso a paso y escribamos un método para agregar un elemento al final de la lista, representando la operación de creación:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Arriba, se muestra la implementación del método para agregar un elemento al final de la lista. Analicemos cómo funciona este método:

Se crea un objeto de la clase Node, llamado newNode, y se inicializa a través del constructor, pasando el data desde los parámetros del método append();
A continuación, se verifica si la lista está vacía y, en ese caso, se reemplaza el primer elemento de la lista (head) por newNode mediante reasignación;
Luego, se añade una sentencia return para salir del método;
Si la lista no está vacía, en este método se crea un nuevo objeto, current, que representa el Node head en este contexto;
Utilizando un bucle while, se itera por toda la lista hasta que current.next sea null, es decir, hasta determinar que el siguiente elemento en la lista está vacío;
Una vez que se encuentra el último elemento no nulo en la lista, se establece su enlace a newNode, agregando así el elemento a nuestra lista.

En otras palabras, el objetivo del método append es establecer el enlace del último elemento al nuevo elemento. De esta manera, se agrega un nuevo elemento a la lista.

Leer

Continuemos; ahora necesitamos implementar la operación de lectura.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

La operación de lectura es bastante sencilla. Es necesario iterar por cada elemento de la lista y mostrarlos en pantalla. En este caso, también se utiliza el marcador de posición current, que se inicializa con el Node head;
A continuación, se establece la condición para el bucle while como current != null y se imprime el campo data en pantalla;
Para iterar por la lista, se utiliza la referencia reasignando current, lo cual se realiza como current = current.next;;
Esto se repite hasta que el Node current quede vacío. Después de esto, se sale del bucle y se continúa con la siguiente línea.

Por cierto, reflexiona sobre cómo reemplazar este bucle while por un bucle do-while. ¿Es posible hacerlo?

Actualización

Ahora, pasemos al método de actualización, que resulta más interesante en su implementación:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Primero, se verifica si este index está en nuestra lista utilizando una sentencia if. Si no es así, se imprime el mensaje "Invalid index" y se finaliza el método. Esto se realiza para evitar errores;
Si el índice está dentro de los límites de nuestra lista, se continúa con el algoritmo habitual. Primero, se crea un objeto de la clase Node llamado current, que se inicializa como el head;
En lugar de utilizar un bucle while, se utiliza un bucle for, que es más adecuado en este caso ya que se conoce el número exacto de iteraciones necesarias. El número de iteraciones es igual al valor del parámetro index;
El bucle se ve así:
for (int i = 0; i < index; i++). En este bucle, se encuentra el elemento deseado utilizando la operación habitual: current = current.next;
Una vez encontrado el elemento deseado, se asigna un nuevo valor a su atributo data, realizando la operación
current.data = newData. El valor de newData se toma de los parámetros de este método.

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 7

Pregunte a AI

Pregunte lo que quiera o pruebe una de las preguntas sugeridas para comenzar nuestra charla

Sección 1. Capítulo 7