Programando listas enlazadas con Java

Clase 3 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Comentarios

Dualwer Gómez

student•

Los métodos de borrarNodo y borrarNodoPorValor al hacer el .siguiente = null; no borra el nodo sino que lo desconecta (borra) la referencia de ahí en adelante. Es necesario tener un apuntador en el anterior para conectarlo al siguiente y no perder el resto de la lista.

Irving Juárez

student•

Esto podría causar un memory leak, ya que el nodo borrado sigue existiendo en memoria. En este caso Java tiene garbage collector, pero otros lenguajes más cercanos a la computadora, como C no tienen este feature

Pro Code

student•

Se puede hacer con el uso de la lógica de buscarNodo.

Irving Juárez, si ese nodo eliminado lo igualo a null se evitaría en memory leak?

Luis Alberto Ramírez Botero

student•

Me falto mas explicacion, se me dificulta entender algoritmos en otros lenguajes que no sea python.

William Rodriguez

student•

El algoritmos es el mismo.

La implementación cambia pero no el algoritmos puede ser en papel y lápiz, python o C el algoritmo es el mismo.

José Ramón García

student•

Aquí te dejo como sería en python

class Nodo:
    def __init__(self, valor, siguiente=None):
        self.valor = valor
        self.siguiente = siguiente  # Puntero al siguiente nodo

class ListaEnlazada:
    def __init__(self, primer_nodo):
        self.cabeza = primer_nodo
        self.cola = primer_nodo

    def insertar_nodo_al_final(self, nuevo_nodo):
        """ Agrega un nodo al final de la lista """
        self.cola.siguiente = nuevo_nodo
        self.cola = nuevo_nodo

    def borrar_nodo(self, nodo):
        """ Borra un nodo (desenlazándolo) """
        nodo.siguiente = None

    def buscar_nodo(self, valor_a_buscar):
        """ Busca un nodo con un valor específico """
        nodo_actual = self.cabeza
        while nodo_actual:
            if nodo_actual.valor == valor_a_buscar:
                return nodo_actual
            nodo_actual = nodo_actual.siguiente
        return None

    def borrar_nodo_por_valor(self, valor):
        """ Busca y elimina un nodo con un valor específico """
        nodo_a_borrar = self.buscar_nodo(valor)
        if nodo_a_borrar:
            nodo_a_borrar.siguiente = None

Walter Oswaldo Pleitez Torres

student•

Se pueden hacer Listas Enlazadas usando Clases de C++?

Miguel Angel Reyes Moreno

student•

hecho por chat gpt

\#include \<iostream>



// Nodo de la lista enlazada

class Node {

public:

&#x20;   int data;

&#x20;   Node\* next;



&#x20;   Node(int data) : data(data), next(nullptr) {}

};



// Clase de lista enlazada

class LinkedList {

private:

&#x20;   Node\* head;



public:

&#x20;   LinkedList() : head(nullptr) {}



&#x20;   // Añadir un nodo al final de la lista

&#x20;   void append(int data) {

&#x20;       Node\* newNode = new Node(data);

&#x20;       if (head == nullptr) {

&#x20;           head = newNode;

&#x20;       } else {

&#x20;           Node\* current = head;

&#x20;           while (current->next != nullptr) {

&#x20;               current = current->next;

&#x20;           }

&#x20;           current->next = newNode;

&#x20;       }

&#x20;   }



&#x20;   // Añadir un nodo al principio de la lista

&#x20;   void prepend(int data) {

&#x20;       Node\* newNode = new Node(data);

&#x20;       newNode->next = head;

&#x20;       head = newNode;

&#x20;   }



&#x20;   // Eliminar un nodo con un valor específico

&#x20;   void remove(int data) {

&#x20;       if (head == nullptr) return;



&#x20;       if (head->data == data) {

&#x20;           Node\* temp = head;

&#x20;           head = head->next;

&#x20;           delete temp;

&#x20;           return;

&#x20;       }



&#x20;       Node\* current = head;

&#x20;       while (current->next != nullptr && current->next->data != data) {

&#x20;           current = current->next;

&#x20;       }



&#x20;       if (current->next != nullptr) {

&#x20;           Node\* temp = current->next;

&#x20;           current->next = current->next->next;

&#x20;           delete temp;

&#x20;       }

&#x20;   }



&#x20;   // Imprimir los elementos de la lista

&#x20;   void printList() {

&#x20;       Node\* current = head;

&#x20;       while (current != nullptr) {

&#x20;           std::cout << current->data << " -> ";

&#x20;           current = current->next;

&#x20;       }

&#x20;       std::cout << "nullptr" << std::endl;

&#x20;   }



&#x20;   // Destructor para liberar la memoria

&#x20;   \~LinkedList() {

&#x20;       Node\* current = head;

&#x20;       while (current != nullptr) {

&#x20;           Node\* temp = current;

&#x20;           current = current->next;

&#x20;           delete temp;

&#x20;       }

&#x20;   }

};



int main() {

&#x20;   LinkedList list;

&#x20;   list.append(10);

&#x20;   list.append(20);

&#x20;   list.append(30);

&#x20;   list.prepend(5);

&#x20;   list.printList();  // Imprime: 5 -> 10 -> 20 -> 30 -> nullptr



&#x20;   list.remove(20);

&#x20;   list.printList();  // Imprime: 5 -> 10 -> 30 -> nullptr



&#x20;   return 0;

}

Ulises Alejandro Mánica Caricio

student•

¿Alguien sabe si es necesario escribir la primera forma o es indistinto y puedo usar cualquiera de las dos?

Lista_enlazada def insertar_nodo_al_final(self, nuevo_nodo: Nodo): self.cola.siguiente = nuevo_nodo self.cola = self.cola.siguiente

Lista_enlazada def insertar_nodo_al_final(self, nuevo_nodo: Nodo): self.cola.siguiente = nuevo_nodo self.cola = nuevo_nodo

Ashley Andres Alejo Guilarte

student•

Si lo estas haciendo en java y tambien tuviste la duda de porque la profe no usa parentesis y eso en el metodo buscarNodo aqui el codigo corregido:

public Nodo buscarNodo(int valorABuscar) {
        Nodo nodoActual = cabeza;
        while (nodoActual != null) {
            if (nodoActual.valor == valorABuscar) {
                return nodoActual;
            }
            nodoActual = nodoActual.siguiente;
        }
        return null;
    }
```public Nodo buscarNodo(int valorABuscar) {
&#x20;   Nodo nodoActual = cabeza;
&#x20;   while (nodoActual != null) {
&#x20;       if (nodoActual.valor == valorABuscar) {
&#x20;           return nodoActual;
&#x20;       }
&#x20;       nodoActual = nodoActual.siguiente;
&#x20;   }
&#x20;   return null;
}

![](https://static.platzi.com/media/user_upload/image-a1e9ed8d-a285-4fbc-85db-7b59531386b6.jpg)

Miguel Angel Reyes Moreno

student•

Se olvidó que estaba usando Java y empezó a usar sintaxís de Python xD

Miguel Angel Reyes Moreno

student•

Les comparto una lista de vídeos de youtube de estruturas de datos con Java:

Hector Vasquez

student•

por lo que entiendo del ejercicio:

borrarNodo y borrarNodoPorValor, no están borrando el nodo especificado, sino que están borrando los enlaces desde el nodo especificado hacia otros nodo (siguiente).

Para borrar el nodo especificado, se debería buscar todos los nodos, cuyo "siguiente" apunta al nodo especificado, asignarle null (desvincularlo)

Hector Vasquez

student•

también vincular el "siguiente" al nodo contiguo al borrado (si existe), para no perder la continuidad de la lista de nodos

Pro Code

student•

Para los que necesiten el código en Python:

https://github.com/NarcisaColcha/Lista-Enlazada-Simple

Una visualización del porque está incompleto el método borrarNodo y borrarNodoPorValor, si la lista fuera: 0 -> 1 -> 2 -> 3 y quisiera eliminar el 1, obtendríamos: 0 -> 1, el resto lo perderíamos ya que no hicimos una conexión (.siguiente) al resto de la lista que estaba después del nodo a eliminar (2 -> 3), para que luego el 0 apunte al resto de la lista.

Nicolas Alpargatero

student•

Muchos la conocen, pero para hacer pruebas y entender mejor us:

https://pythontutor.com/render.html#mode=display

Tambien comparto el código en python, pero modificándole el delate, porque el de la profe tiene un Bug o al menos al pasarlo a python no elimina bien:

para hacer pruebas:

# Create a new linked list with the first node
first_node = Node(1)
linked_list = LinkedList(first_node)

# Insert a new node at the end of the linked lis
second_node = Node(2)
linked_list.insert_node_at_end(second_node)

found_node = linked_list.search_node(2)
print(found_node.value)

linked_list.delete_node_by_value(2)

found_node = linked_list.search_node(2)
print(found_node) # This should print None

Pro Code

student•

Solución más compleja en Java mismo del método borrarNodoPorValor y para ir observando cómo va quedando la lista sobreescribí el método toString, ambos van en la clase ListaEnlazada:

    public void borrarNodoPorValor(int valor) {
        
        if (cabeza == null) { // Si la lista enlazada está vacía
            System.out.println("El nodo no pudo ser borrado porque la ListaEnlazada está vacía.");
        } else {
            Nodo nodoABorrar = buscarNodo(valor);

            if (nodoABorrar != null) {
                Nodo nuevo = null;

                if ((cabeza.equals(cola))) { // Si la lista enlazada tiene solo 1 nodo
                    cabeza = null;
                    System.out.println("ListaEnlazada ahora está vacía.");    
                } else if (nodoABorrar == cabeza) {
                    nuevo = cabeza.siguiente;
                    nodoABorrar.siguiente = null;
                    cabeza = nuevo;
                    cabeza.siguiente = nuevo.siguiente;                
                } else {   // Cualquier nodo después de cabeza, incluido cola

                    Nodo nodoAnterior = null;
                    Nodo nodoActual = cabeza;
                    
                    while(nodoActual.siguiente != null) {
                        nodoAnterior = nodoActual;
                        nodoActual = nodoActual.siguiente;
                        if ((nodoActual == nodoABorrar) && (nodoABorrar != cola)) {
                            break;
                        }
                    }                       
                        
                    if (nodoABorrar != cola) {
                        nodoAnterior.siguiente = nodoActual.siguiente;
                        nodoActual.siguiente = null;
                        nodoActual = null;
                    } else {                    // Si es igual a cola
                        cola = nodoAnterior;
                        cola.siguiente = null;
                    }
                } 
            } else {
                System.out.println("Nodo no existente.");
            }
        }    
    }
    
    
    @Override
    public String toString() {
        if (cabeza == null) { //Si la lista en vacía
            return "ListaEnlazada{}";
        } else if (cabeza != null && cabeza == cola) { // Si la lista tiene solo 1 elemento
            return "ListaEnlazada{cabeza:" + cabeza.valor + ", cola: " + cola.valor + "}";
        }
        return "ListaEnlazada{cabeza=" + cabeza.valor + ", cabeza.siguiente=" + cabeza.siguiente.valor + ", cola=" + cola.valor + "}";
    }

GUSTAVO CHIAPPE

student•

Hola , Muy bueno el comienzo , pero estaría bueno que haya una pausa creando nodos (haciendo correr código del nodo ) y después pasar a la class ListaEnlazada .

Pro Code

student•

Puedes hacerlo en Java sobreescribiendo el método toString:

    @Override
    public String toString() {
        if (cabeza == null) { //Si la lista en vacía
            return "ListaEnlazada{}";
        } else if (cabeza != null && cabeza == cola) { // Si la lista tiene solo 1 elemento
            return "ListaEnlazada{cabeza:" + cabeza.valor + ", cola: " + cola.valor + "}";
        }
        return "ListaEnlazada{cabeza=" + cabeza.valor + ", cabeza.siguiente=" + cabeza.siguiente.valor + ", cola=" + cola.valor + "}";
    }

Pro Code

student•

Te dejo también la llamada en el main (public static void main(String[] args)), con las clases Nodo y ListaEnlazada por separado:

        Nodo n1 = new Nodo(1);
        ListaEnlazada le = new ListaEnlazada(n1);
        Nodo n2 = new Nodo(2);
        le.insertarNodoAlFinal(n2);
        le.insertarNodoAlFinal(new Nodo(3));
        le.borrarNodoPorValor(2);
        System.out.println(le.toString());

José David Jayk Vanegas

student•

Creo que el método borrarNodoPorValor podria utilizar el método borrarNodo que ya tenemos

public void borrarNodoPorValor(int valor){
	nodoABorrar = buscarNodo(valor);
	if(nodoABorrar != null){
		borrarNodo(nodoABorrar);
	}
}

class Nodo:
    def __init__(self, valor, siguiente=None):
        self.valor = valor
        self.siguiente = siguiente  # Puntero al siguiente nodo

class ListaEnlazada:
    def __init__(self, primer_nodo):
        self.cabeza = primer_nodo
        self.cola = primer_nodo

    def insertar_nodo_al_final(self, nuevo_nodo):
        """ Agrega un nodo al final de la lista """
        self.cola.siguiente = nuevo_nodo
        self.cola = nuevo_nodo

    def borrar_nodo(self, nodo):
        """ Borra un nodo (desenlazándolo) """
        nodo.siguiente = None

    def buscar_nodo(self, valor_a_buscar):
        """ Busca un nodo con un valor específico """
        nodo_actual = self.cabeza
        while nodo_actual:
            if nodo_actual.valor == valor_a_buscar:
                return nodo_actual
            nodo_actual = nodo_actual.siguiente
        return None

    def borrar_nodo_por_valor(self, valor):
        """ Busca y elimina un nodo con un valor específico """
        nodo_a_borrar = self.buscar_nodo(valor)
        if nodo_a_borrar:
            nodo_a_borrar.siguiente = None

\#include \<iostream>

// Nodo de la lista enlazada

class Node {

public:

&#x20;   int data;

&#x20;   Node\* next;

&#x20;   Node(int data) : data(data), next(nullptr) {}

};

// Clase de lista enlazada

class LinkedList {

private:

&#x20;   Node\* head;

public:

&#x20;   LinkedList() : head(nullptr) {}

&#x20;   // Añadir un nodo al final de la lista

&#x20;   void append(int data) {

&#x20;       Node\* newNode = new Node(data);

&#x20;       if (head == nullptr) {

&#x20;           head = newNode;

&#x20;       } else {

&#x20;           Node\* current = head;

&#x20;           while (current->next != nullptr) {

&#x20;               current = current->next;

&#x20;           }

&#x20;           current->next = newNode;

&#x20;       }

&#x20;   }

&#x20;   // Añadir un nodo al principio de la lista

&#x20;   void prepend(int data) {

&#x20;       Node\* newNode = new Node(data);

&#x20;       newNode->next = head;

&#x20;       head = newNode;

&#x20;   }

&#x20;   // Eliminar un nodo con un valor específico

&#x20;   void remove(int data) {

&#x20;       if (head == nullptr) return;

&#x20;       if (head->data == data) {

&#x20;           Node\* temp = head;

&#x20;           head = head->next;

&#x20;           delete temp;

&#x20;           return;

&#x20;       }

&#x20;       Node\* current = head;

&#x20;       while (current->next != nullptr && current->next->data != data) {

&#x20;           current = current->next;

&#x20;       }

&#x20;       if (current->next != nullptr) {

&#x20;           Node\* temp = current->next;

&#x20;           current->next = current->next->next;

&#x20;           delete temp;

&#x20;       }

&#x20;   }

&#x20;   // Imprimir los elementos de la lista

&#x20;   void printList() {

&#x20;       Node\* current = head;

&#x20;       while (current != nullptr) {

&#x20;           std::cout << current->data << " -> ";

&#x20;           current = current->next;

&#x20;       }

&#x20;       std::cout << "nullptr" << std::endl;

&#x20;   }

&#x20;   // Destructor para liberar la memoria

&#x20;   \~LinkedList() {

&#x20;       Node\* current = head;

&#x20;       while (current != nullptr) {

&#x20;           Node\* temp = current;

&#x20;           current = current->next;

&#x20;           delete temp;

&#x20;       }

&#x20;   }

};

int main() {

&#x20;   LinkedList list;

&#x20;   list.append(10);

&#x20;   list.append(20);

&#x20;   list.append(30);

&#x20;   list.prepend(5);

&#x20;   list.printList();  // Imprime: 5 -> 10 -> 20 -> 30 -> nullptr

&#x20;   list.remove(20);

&#x20;   list.printList();  // Imprime: 5 -> 10 -> 30 -> nullptr

&#x20;   return 0;

}

public Nodo buscarNodo(int valorABuscar) {
        Nodo nodoActual = cabeza;
        while (nodoActual != null) {
            if (nodoActual.valor == valorABuscar) {
                return nodoActual;
            }
            nodoActual = nodoActual.siguiente;
        }
        return null;
    }
```public Nodo buscarNodo(int valorABuscar) {
&#x20;   Nodo nodoActual = cabeza;
&#x20;   while (nodoActual != null) {
&#x20;       if (nodoActual.valor == valorABuscar) {
&#x20;           return nodoActual;
&#x20;       }
&#x20;       nodoActual = nodoActual.siguiente;
&#x20;   }
&#x20;   return null;
}

![](https://static.platzi.com/media/user_upload/image-a1e9ed8d-a285-4fbc-85db-7b59531386b6.jpg)

    public void borrarNodoPorValor(int valor) {
        
        if (cabeza == null) { // Si la lista enlazada está vacía
            System.out.println("El nodo no pudo ser borrado porque la ListaEnlazada está vacía.");
        } else {
            Nodo nodoABorrar = buscarNodo(valor);

            if (nodoABorrar != null) {
                Nodo nuevo = null;

                if ((cabeza.equals(cola))) { // Si la lista enlazada tiene solo 1 nodo
                    cabeza = null;
                    System.out.println("ListaEnlazada ahora está vacía.");    
                } else if (nodoABorrar == cabeza) {
                    nuevo = cabeza.siguiente;
                    nodoABorrar.siguiente = null;
                    cabeza = nuevo;
                    cabeza.siguiente = nuevo.siguiente;                
                } else {   // Cualquier nodo después de cabeza, incluido cola

                    Nodo nodoAnterior = null;
                    Nodo nodoActual = cabeza;
                    
                    while(nodoActual.siguiente != null) {
                        nodoAnterior = nodoActual;
                        nodoActual = nodoActual.siguiente;
                        if ((nodoActual == nodoABorrar) && (nodoABorrar != cola)) {
                            break;
                        }
                    }                       
                        
                    if (nodoABorrar != cola) {
                        nodoAnterior.siguiente = nodoActual.siguiente;
                        nodoActual.siguiente = null;
                        nodoActual = null;
                    } else {                    // Si es igual a cola
                        cola = nodoAnterior;
                        cola.siguiente = null;
                    }
                } 
            } else {
                System.out.println("Nodo no existente.");
            }
        }    
    }
    
    
    @Override
    public String toString() {
        if (cabeza == null) { //Si la lista en vacía
            return "ListaEnlazada{}";
        } else if (cabeza != null && cabeza == cola) { // Si la lista tiene solo 1 elemento
            return "ListaEnlazada{cabeza:" + cabeza.valor + ", cola: " + cola.valor + "}";
        }
        return "ListaEnlazada{cabeza=" + cabeza.valor + ", cabeza.siguiente=" + cabeza.siguiente.valor + ", cola=" + cola.valor + "}";
    }

    @Override
    public String toString() {
        if (cabeza == null) { //Si la lista en vacía
            return "ListaEnlazada{}";
        } else if (cabeza != null && cabeza == cola) { // Si la lista tiene solo 1 elemento
            return "ListaEnlazada{cabeza:" + cabeza.valor + ", cola: " + cola.valor + "}";
        }
        return "ListaEnlazada{cabeza=" + cabeza.valor + ", cabeza.siguiente=" + cabeza.siguiente.valor + ", cola=" + cola.valor + "}";
    }

        Nodo n1 = new Nodo(1);
        ListaEnlazada le = new ListaEnlazada(n1);
        Nodo n2 = new Nodo(2);
        le.insertarNodoAlFinal(n2);
        le.insertarNodoAlFinal(new Nodo(3));
        le.borrarNodoPorValor(2);
        System.out.println(le.toString()); 

Programando listas enlazadas con Java

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada