El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Listas Enlazadas

Siguiente ►
►

Introducción

Las listas enlazadas son una estructura de datos fundamental que permite almacenar una colección de elementos de manera secuencial. A diferencia de los arrays, las listas enlazadas no requieren un bloque contiguo de memoria, lo que las hace más flexibles en términos de inserción y eliminación de elementos.

Conceptos Clave

  • Nodo: La unidad básica de una lista enlazada. Cada nodo contiene dos partes: el dato y una referencia (o enlace) al siguiente nodo en la secuencia.
  • Cabeza (Head): El primer nodo de la lista enlazada.
  • Cola (Tail): El último nodo de la lista enlazada, cuya referencia al siguiente nodo es null.

Tipos de Listas Enlazadas

  1. Lista Enlazada Simple: Cada nodo apunta al siguiente nodo.
  2. Lista Doblemente Enlazada: Cada nodo tiene dos referencias, una al siguiente nodo y otra al nodo anterior.
  3. Lista Circular: El último nodo apunta de nuevo al primer nodo, formando un ciclo.

Estructura de una Lista Enlazada Simple

Nodo

class Nodo:
    def __init__(self, dato):
        self.dato = dato
        self.siguiente = None

Lista Enlazada

class ListaEnlazada:
    def __init__(self):
        self.cabeza = None

    def insertar_al_inicio(self, dato):
        nuevo_nodo = Nodo(dato)
        nuevo_nodo.siguiente = self.cabeza
        self.cabeza = nuevo_nodo

    def insertar_al_final(self, dato):
        nuevo_nodo = Nodo(dato)
        if self.cabeza is None:
            self.cabeza = nuevo_nodo
            return
        ultimo = self.cabeza
        while ultimo.siguiente:
            ultimo = ultimo.siguiente
        ultimo.siguiente = nuevo_nodo

    def eliminar_nodo(self, key):
        temp = self.cabeza
        if temp is not None:
            if temp.dato == key:
                self.cabeza = temp.siguiente
                temp = None
                return
        while temp is not None:
            if temp.dato == key:
                break
            prev = temp
            temp = temp.siguiente
        if temp == None:
            return
        prev.siguiente = temp.siguiente
        temp = None

    def buscar(self, key):
        temp = self.cabeza
        while temp is not None:
            if temp.dato == key:
                return True
            temp = temp.siguiente
        return False

    def imprimir_lista(self):
        temp = self.cabeza
        while temp:
            print(temp.dato, end=" -> ")
            temp = temp.siguiente
        print("None")

Explicación del Código

  1. Clase Nodo:

    • __init__(self, dato): Inicializa el nodo con el dato y establece la referencia siguiente a None.

  2. Clase ListaEnlazada:

    • __init__(self): Inicializa la lista con la cabeza (cabeza) como None.
    • insertar_al_inicio(self, dato): Inserta un nuevo nodo al inicio de la lista.
    • insertar_al_final(self, dato): Inserta un nuevo nodo al final de la lista.
    • eliminar_nodo(self, key): Elimina el primer nodo que contiene el dato key.
    • buscar(self, key): Busca un nodo con el dato key en la lista.
    • imprimir_lista(self): Imprime todos los nodos de la lista.

Ejemplo Práctico

# Crear una lista enlazada
lista = ListaEnlazada()

# Insertar elementos
lista.insertar_al_inicio(3)
lista.insertar_al_inicio(2)
lista.insertar_al_inicio(1)
lista.insertar_al_final(4)

# Imprimir la lista
lista.imprimir_lista()  # Salida: 1 -> 2 -> 3 -> 4 -> None

# Buscar un elemento
print(lista.buscar(3))  # Salida: True
print(lista.buscar(5))  # Salida: False

# Eliminar un elemento
lista.eliminar_nodo(3)
lista.imprimir_lista()  # Salida: 1 -> 2 -> 4 -> None

Ejercicios

Ejercicio 1: Inserción en una Lista Enlazada

Instrucciones: Implementa una función insertar_despues(self, prev_dato, dato) en la clase ListaEnlazada que inserte un nuevo nodo después de un nodo con un dato específico (prev_dato).

def insertar_despues(self, prev_dato, dato):
    temp = self.cabeza
    while temp is not None:
        if temp.dato == prev_dato:
            break
        temp = temp.siguiente
    if temp is None:
        print("El nodo con el dato", prev_dato, "no está en la lista.")
        return
    nuevo_nodo = Nodo(dato)
    nuevo_nodo.siguiente = temp.siguiente
    temp.siguiente = nuevo_nodo

Solución:

# Añadir el método a la clase ListaEnlazada
ListaEnlazada.insertar_despues = insertar_despues

# Crear una lista enlazada y probar la nueva función
lista = ListaEnlazada()
lista.insertar_al_inicio(3)
lista.insertar_al_inicio(2)
lista.insertar_al_inicio(1)
lista.insertar_despues(2, 2.5)
lista.imprimir_lista()  # Salida: 1 -> 2 -> 2.5 -> 3 -> None

Ejercicio 2: Reversión de una Lista Enlazada

Instrucciones: Implementa una función revertir_lista(self) en la clase ListaEnlazada que revierta la lista enlazada.

def revertir_lista(self):
    prev = None
    current = self.cabeza
    while current is not None:
        next_node = current.siguiente
        current.siguiente = prev
        prev = current
        current = next_node
    self.cabeza = prev

Solución:

# Añadir el método a la clase ListaEnlazada
ListaEnlazada.revertir_lista = revertir_lista

# Crear una lista enlazada y probar la nueva función
lista = ListaEnlazada()
lista.insertar_al_inicio(3)
lista.insertar_al_inicio(2)
lista.insertar_al_inicio(1)
lista.imprimir_lista()  # Salida: 1 -> 2 -> 3 -> None
lista.revertir_lista()
lista.imprimir_lista()  # Salida: 3 -> 2 -> 1 -> None

Conclusión

En esta sección, hemos aprendido sobre las listas enlazadas, su estructura y cómo implementarlas en Python. Hemos cubierto las operaciones básicas como inserción, eliminación y búsqueda, y hemos practicado con ejercicios para reforzar los conceptos. Las listas enlazadas son una herramienta poderosa y flexible que se utiliza en muchas aplicaciones de programación.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2024. Todos los derechos reservados