Aprende Implementación de LinkedList en Java | Estructuras de Datos Fundamentales en Java

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, se crea la clase SinglyLinkedList, donde se definirá toda la lógica para nuestra estructura de datos:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Se creó el campo Node head, que almacenará el primer elemento de nuestra estructura de datos.

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

Nuestra estructura de datos debe soportar todas las operaciones CRUD.

Crear

A continuación, 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, si es así, se reemplaza el primer elemento de la lista (head) por newNode mediante reasignación;
Luego, se agrega 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 a través de 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 Node head;
A continuación, se establece la condición para el bucle while como current != null y se muestra el campo data en pantalla;
Para iterar por la lista, se utiliza la referencia reasignando current, lo que se ve como current = current.next;;
Esto se repite hasta que Node current queda vacío. Después de esto, se sale del bucle y se continúa con la siguiente línea.

Por cierto, reflexione 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, cuya implementación resulta más interesante:

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 la 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 la 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 emplea 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 presenta de la siguiente manera:
for (int i = 0; i < index; i++). En este bucle, se localiza el elemento deseado mediante la operación habitual: current = current.next;
Una vez localizado el elemento, 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 6

Pregunte a AI

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

Suggested prompts:

Can you show me the code for the append method?

How would you implement the read operation in code?

Can you explain how the update method works with an example?

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, se crea la clase SinglyLinkedList, donde se definirá toda la lógica para nuestra estructura de datos:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Se creó el campo Node head, que almacenará el primer elemento de nuestra estructura de datos.

Nuestra estructura de datos debe soportar todas las operaciones CRUD.

Crear

A continuación, 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, si es así, se reemplaza el primer elemento de la lista (head) por newNode mediante reasignación;
Luego, se agrega 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 a través de 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 Node head;
A continuación, se establece la condición para el bucle while como current != null y se muestra el campo data en pantalla;
Para iterar por la lista, se utiliza la referencia reasignando current, lo que se ve como current = current.next;;
Esto se repite hasta que Node current queda vacío. Después de esto, se sale del bucle y se continúa con la siguiente línea.

Por cierto, reflexione 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, cuya implementación resulta más interesante:

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 la 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 la 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 emplea 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 presenta de la siguiente manera:
for (int i = 0; i < index; i++). En este bucle, se localiza el elemento deseado mediante la operación habitual: current = current.next;
Una vez localizado el elemento, 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 6