Introducción

Las listas circulares son una variación de las listas enlazadas en las que el último nodo apunta de nuevo al primer nodo, formando un ciclo. Esta estructura permite recorrer la lista de manera continua sin necesidad de llegar a un final explícito.

Características de las Listas Circulares

Ciclo Continuo: El último nodo de la lista apunta al primer nodo, creando un ciclo.
Acceso Secuencial: Se puede recorrer la lista desde cualquier nodo y eventualmente se llegará de nuevo al nodo inicial.
No hay Nodo Nulo: A diferencia de las listas enlazadas simples, no hay un nodo que apunte a null o None.

Tipos de Listas Circulares

Lista Circular Simple: Cada nodo tiene un enlace al siguiente nodo, y el último nodo apunta al primero.
Lista Circular Doblemente Enlazada: Cada nodo tiene enlaces tanto al siguiente como al nodo anterior, y el último nodo apunta al primero y viceversa.

Implementación de una Lista Circular Simple

Estructura del Nodo

Primero, definimos la estructura del nodo:

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

Clase de la Lista Circular

Ahora, implementamos la clase de la lista circular:

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

    def agregar(self, dato):
        nuevo_nodo = Nodo(dato)
        if not self.cabeza:
            self.cabeza = nuevo_nodo
            self.cabeza.siguiente = self.cabeza
        else:
            temp = self.cabeza
            while temp.siguiente != self.cabeza:
                temp = temp.siguiente
            temp.siguiente = nuevo_nodo
            nuevo_nodo.siguiente = self.cabeza

    def mostrar(self):
        if not self.cabeza:
            print("La lista está vacía")
            return
        temp = self.cabeza
        while True:
            print(temp.dato, end=" -> ")
            temp = temp.siguiente
            if temp == self.cabeza:
                break
        print("(cabeza)")

# Ejemplo de uso
lista = ListaCircular()
lista.agregar(1)
lista.agregar(2)
lista.agregar(3)
lista.mostrar()

Explicación del Código

Clase Nodo: Define un nodo con un dato y un puntero al siguiente nodo.
Clase ListaCircular:
- __init__: Inicializa la lista con una cabeza vacía.
- agregar: Añade un nuevo nodo a la lista. Si la lista está vacía, el nuevo nodo se convierte en la cabeza y su siguiente apunta a sí mismo. Si no, se recorre la lista hasta el último nodo y se actualiza para que el nuevo nodo apunte a la cabeza.
- mostrar: Recorre la lista desde la cabeza y muestra los datos de cada nodo hasta volver a la cabeza.

Ejercicio Práctico

Ejercicio 1: Eliminar un Nodo en una Lista Circular

Implementa una función para eliminar un nodo específico en una lista circular.

class ListaCircular:
    # ... (código anterior)

    def eliminar(self, dato):
        if not self.cabeza:
            print("La lista está vacía")
            return

        temp = self.cabeza
        anterior = None

        while True:
            if temp.dato == dato:
                if anterior:
                    anterior.siguiente = temp.siguiente
                else:
                    # Si estamos eliminando la cabeza
                    if temp.siguiente == self.cabeza:
                        self.cabeza = None
                    else:
                        self.cabeza = temp.siguiente
                        ultimo = self.cabeza
                        while ultimo.siguiente != temp:
                            ultimo = ultimo.siguiente
                        ultimo.siguiente = self.cabeza
                return
            anterior = temp
            temp = temp.siguiente
            if temp == self.cabeza:
                break
        print(f"El dato {dato} no se encuentra en la lista")

# Ejemplo de uso
lista = ListaCircular()
lista.agregar(1)
lista.agregar(2)
lista.agregar(3)
lista.mostrar()
lista.eliminar(2)
lista.mostrar()

Solución del Ejercicio

Eliminar Nodo: La función eliminar recorre la lista buscando el nodo con el dato especificado. Si lo encuentra, actualiza los punteros para eliminar el nodo. Si el nodo a eliminar es la cabeza, se actualiza la cabeza y se ajusta el puntero del último nodo.
Caso Especial: Si la lista está vacía o el dato no se encuentra, se imprime un mensaje adecuado.

Conclusión

Las listas circulares son una estructura útil para situaciones donde se requiere un acceso continuo y cíclico a los elementos. Su implementación y manipulación requieren atención especial para manejar correctamente los punteros y evitar ciclos infinitos.

En el siguiente módulo, exploraremos las pilas, otra estructura de datos fundamental en la programación.

Listas Circulares

Introducción

Características de las Listas Circulares

Tipos de Listas Circulares

Implementación de una Lista Circular Simple

Estructura del Nodo

Clase de la Lista Circular

Explicación del Código

Ejercicio Práctico

Ejercicio 1: Eliminar un Nodo en una Lista Circular

Solución del Ejercicio

Conclusión

Curso de Estructuras de Datos

Módulo 1: Introducción a las Estructuras de Datos

Módulo 2: Listas

Módulo 3: Pilas

Módulo 4: Colas

Módulo 5: Árboles

Módulo 6: Grafos

Módulo 7: Conclusiones y Recursos Adicionales