Es hora de desafiarte a ti mismo con algunas tareas realmente complejas. En este capítulo, implementaremos nuestra estructura de datos simplificada - específicamente, la SinglyLinkedList.

Empecemos 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;
    }
}

En el capítulo anterior, ya demostré la implementación de la clase Node en SinglyLinkedList, así que no nos detendremos mucho en ello.

A continuación, vamos a crear la clase SinglyLinkedList, donde definiremos toda la lógica de 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 normal, también hay una head y una 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, inicializamos este campo como null en el constructor.

Necesitamos que nuestra estructura de datos tenga todas las operaciones CRUD.

Crear

Así que, vayamos paso a paso y escribamos un método para añadir un elemento al final de la lista, representando la operación Crear:

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 puedes ver la implementación del método para añadir un elemento al final de la lista. Vamos a desglosar cómo funciona este método:
Creamos un objeto de la clase Node, newNode, y lo inicializamos a través del constructor, pasándole los data de los parámetros del método append().
A continuación, comprobamos si la lista está vacía, y si lo está, reemplazamos el primer elemento de la lista (head) por newNode mediante reasignación.
A continuación, añadimos una sentencia return para salir del método.
Si la lista no está vacía, en este método creamos un nuevo objeto, current, que representa al Node head en este contexto.
Usando un bucle while, iteramos a través de toda la lista hasta que current.next es null, es decir, hasta que determinamos que el siguiente elemento de la lista está vacío.
Una vez que encontramos el último elemento no nulo de la lista, establecemos su enlace a newNode, añadiendo así el elemento a nuestra lista.

En otras palabras, el objetivo del método append era establecer el enlace del último elemento al nuevo elemento. De esta forma, añadimos un nuevo elemento a la lista.

Leer

Sigamos adelante; 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. Necesitamos iterar a través de cada elemento de la lista e imprimirlos en la pantalla. En nuestro caso, también utilizamos el marcador de posición current, que inicializamos con el Node head.
A continuación, establecemos la condición para el bucle while a current != null e imprimimos el campo data en la pantalla.
Para iterar por la lista, utilizamos la referencia reasignando current, que queda como current = current.next;.
Hacemos esto hasta que el "Nodo actual" se vacía. Después de esto, salimos del bucle y pasamos a la siguiente línea.

Por cierto, piensa en cómo sustituir este bucle while por un bucle do-while. ¿Se puede hacer?

Actualización

Ahora, pasemos al método update, que es 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;
}

Nota

En este método, usamos el método size, que implementarás tú mismo en el próximo capítulo. Así que, por ahora, es importante entender que este método devuelve la longitud de la lista.

Primero, comprobamos si este index está en nuestra lista usando una sentencia if. Si no, imprimimos el mensaje "Índice no válido" y terminamos el método. Esto se hace para evitar errores.

Si el índice está dentro de los límites de nuestra lista, procedemos con el algoritmo conocido. Primero, creamos un objeto de la clase Node llamado current, que inicializamos como head.

En lugar de utilizar un bucle while, utilizamos un bucle for, que es más adecuado en este caso ya que sabemos el número exacto de iteraciones que necesitamos. El número de iteraciones es igual al valor del parámetro index.

Nuestro bucle tiene el siguiente aspecto:
for (int i = 0; i < index; i++). En este bucle, encontramos el elemento deseado utilizando la operación familiar: actual = actual.siguiente.

Una vez encontrado el elemento deseado, asignamos a su atributo data un nuevo valor, realizando la operación
current.data = newData. Tomamos newData de los parámetros de este método.

Parece bastante sencillo, ¿verdad? Te dejo como tarea implementar dos métodos en esta clase: el método delete y el método size. Estoy seguro de que te harás cargo de esta tarea. Nos vemos en el próximo capítulo.

¿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

Desliza para mostrar el menú

Es hora de desafiarte a ti mismo con algunas tareas realmente complejas. En este capítulo, implementaremos nuestra estructura de datos simplificada - específicamente, la SinglyLinkedList.

Empecemos 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;
    }
}

En el capítulo anterior, ya demostré la implementación de la clase Node en SinglyLinkedList, así que no nos detendremos mucho en ello.

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

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

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

Necesitamos que nuestra estructura de datos tenga todas las operaciones CRUD.

Crear

Así que, vayamos paso a paso y escribamos un método para añadir un elemento al final de la lista, representando la operación Crear:

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 puedes ver la implementación del método para añadir un elemento al final de la lista. Vamos a desglosar cómo funciona este método:
Creamos un objeto de la clase Node, newNode, y lo inicializamos a través del constructor, pasándole los data de los parámetros del método append().
A continuación, comprobamos si la lista está vacía, y si lo está, reemplazamos el primer elemento de la lista (head) por newNode mediante reasignación.
A continuación, añadimos una sentencia return para salir del método.
Si la lista no está vacía, en este método creamos un nuevo objeto, current, que representa al Node head en este contexto.
Usando un bucle while, iteramos a través de toda la lista hasta que current.next es null, es decir, hasta que determinamos que el siguiente elemento de la lista está vacío.
Una vez que encontramos el último elemento no nulo de la lista, establecemos su enlace a newNode, añadiendo así el elemento a nuestra lista.

En otras palabras, el objetivo del método append era establecer el enlace del último elemento al nuevo elemento. De esta forma, añadimos un nuevo elemento a la lista.

Leer

Sigamos adelante; 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. Necesitamos iterar a través de cada elemento de la lista e imprimirlos en la pantalla. En nuestro caso, también utilizamos el marcador de posición current, que inicializamos con el Node head.
A continuación, establecemos la condición para el bucle while a current != null e imprimimos el campo data en la pantalla.
Para iterar por la lista, utilizamos la referencia reasignando current, que queda como current = current.next;.
Hacemos esto hasta que el "Nodo actual" se vacía. Después de esto, salimos del bucle y pasamos a la siguiente línea.

Por cierto, piensa en cómo sustituir este bucle while por un bucle do-while. ¿Se puede hacer?

Actualización

Ahora, pasemos al método update, que es 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;
}

Nota

En este método, usamos el método size, que implementarás tú mismo en el próximo capítulo. Así que, por ahora, es importante entender que este método devuelve la longitud de la lista.

Primero, comprobamos si este index está en nuestra lista usando una sentencia if. Si no, imprimimos el mensaje "Índice no válido" y terminamos el método. Esto se hace para evitar errores.

Si el índice está dentro de los límites de nuestra lista, procedemos con el algoritmo conocido. Primero, creamos un objeto de la clase Node llamado current, que inicializamos como head.

Nuestro bucle tiene el siguiente aspecto:
for (int i = 0; i < index; i++). En este bucle, encontramos el elemento deseado utilizando la operación familiar: actual = actual.siguiente.

Una vez encontrado el elemento deseado, asignamos a su atributo data un nuevo valor, realizando la operación
current.data = newData. Tomamos newData de los parámetros de este método.

¿Todo estuvo claro?

¡Gracias por tus comentarios!

Sección 1. Capítulo 6

Implementando nuestra LinkedList

Crear

Leer

Actualización

Awesome!

Implementando nuestra LinkedList

Crear

Leer

Actualización