Las Listas Circulares Simplemente Enlazadas son una estructura de datos fundamental. En este artículo te mostraré como implementar una paso a paso en lenguaje C.
Para comprender mejor los diferentes enfoques en la creación de estructuras de datos, podría interesarte revisar la «Creación de una Pila (Stack) en C Utilizando Arreglos«. Aunque utilizar arreglos permite crear una pila de manera sencilla, las listas enlazadas destacan cuando la cantidad de elementos es desconocida o se requieren inserciones y eliminaciones eficientes.
¿Qué es una Lista Circular Simplemente Enlazada?
Una lista enlazada es una colección lineal de elementos, llamados nodos, donde cada nodo apunta al siguiente nodo en la secuencia.
- Simplemente Enlazada: Significa que cada nodo solo tiene un puntero, que apunta al siguiente nodo en la lista. No hay un puntero hacia el nodo anterior.
- Circular: A diferencia de una lista enlazada lineal estándar donde el último nodo apunta a
NULL, en una lista circular, el último nodo apunta de nuevo al primer nodo (la «cabeza» de la lista). Esto crea un bucle o círculo.
Ventajas:
- Se puede recorrer toda la lista comenzando desde cualquier nodo.
- Útil para aplicaciones que requieren un ciclo continuo o un buffer circular (por ejemplo, la gestión de turnos en un juego o procesos en un sistema operativo).
- Algunas operaciones, como la inserción o eliminación al final, pueden volverse más eficientes si se mantiene un puntero al último nodo, ya que este da acceso directo tanto al final como al inicio.
Desventajas:
- Hay que tener cuidado al recorrerla para no caer en un bucle infinito.
- El acceso a un elemento por índice no es directo (requiere recorrer la lista).
Preparando el Entorno en C
Para nuestro programa en C, necesitaremos las bibliotecas estándar que nos proveen funciones esenciales:
stdio.h: Para funciones de entrada/salida estándar, comoprintf.stdlib.h: Para funciones de utilidad general, incluyendo la gestión de memoria dinámica (mallocyfree).
Asegúrate de tener estas líneas al inicio de tu archivo .c:
#include <stdio.h>
#include <stdlib.h>
Definiendo la Estructura del Nodo
Cada elemento en nuestra lista enlazada será un «nodo». Este nodo contendrá dos partes principales:
dato: El valor que queremos almacenar en el nodo (para este ejemplo, será un entero).siguiente: Un puntero al siguiente nodo en la lista.
struct Nodo {
int dato;
struct Nodo* siguiente;
};
Para manejar nuestra lista circular, a menudo es útil tener un puntero que siempre apunte al último nodo insertado o a un nodo de referencia (como la «cabeza», aunque en una lista circular pura, la «cabeza» es más un concepto de punto de entrada). Para este tutorial, usaremos un puntero que llamaremos ultimo, que apuntará al último nodo de la lista. Si la lista está vacía, ultimo será NULL.
Funciones Esenciales
1. Creando un Nuevo Nodo (crearNodo)
Esta función auxiliar tomará un dato, creará un nuevo nodo con ese dato y devolverá un puntero al nodo recién creado.
// Crea un nuevo nodo con el dato proporcionado
struct Nodo* crearNodo(int dato) {
struct Nodo* nuevoNodo = (struct Nodo*)malloc(sizeof(struct Nodo));
if (nuevoNodo == NULL) {
perror("Error: No se pudo asignar memoria para el nuevo nodo");
return NULL; // Falló la asignación
}
nuevoNodo->dato = dato;
nuevoNodo->siguiente = NULL; // Inicialmente, el nuevo nodo no apunta a nada
return nuevoNodo;
}
2. Insertar Elementos
Hay varias formas de insertar elementos. Nos centraremos en insertar al final, ya que es una operación común y eficiente en listas circulares si mantenemos un puntero al último nodo.
Insertar al Final (insertarAlFinal)
Si la lista está vacía, el nuevo nodo se convierte en el único nodo, apuntándose a sí mismo. Si la lista no está vacía, el nuevo nodo se inserta después del nodo ultimo actual, y el nuevo nodo se convierte en el nuevo ultimo.
// Inserta un nodo al final de la lista circular
// Devuelve el puntero al (posiblemente nuevo) último nodo
struct Nodo* insertarAlFinal(struct Nodo* ultimo, int dato) {
struct Nodo* nuevoNodo = crearNodo(dato);
if (nuevoNodo == NULL) {
return ultimo; // No se pudo crear el nodo, la lista no cambia
}
if (ultimo == NULL) { // La lista está vacía
ultimo = nuevoNodo;
ultimo->siguiente = ultimo; // El único nodo apunta a sí mismo
} else { // La lista no está vacía
nuevoNodo->siguiente = ultimo->siguiente; // El nuevo nodo apunta al que era el primero
ultimo->siguiente = nuevoNodo; // El antiguo último nodo apunta al nuevo nodo
ultimo = nuevoNodo; // El nuevo nodo es ahora el último
}
printf("Elemento %d insertado al final.\n", dato);
return ultimo;
}
Insertar al Inicio (insertarAlInicio)
Aunque tengamos un puntero ultimo, insertar al inicio también es factible.
// Inserta un nodo al inicio de la lista circular
// Devuelve el puntero al último nodo (que no cambia en este caso,
// a menos que la lista estuviera vacía)
struct Nodo* insertarAlInicio(struct Nodo* ultimo, int dato) {
struct Nodo* nuevoNodo = crearNodo(dato);
if (nuevoNodo == NULL) {
return ultimo;
}
if (ultimo == NULL) { // La lista está vacía
ultimo = nuevoNodo;
ultimo->siguiente = ultimo;
} else { // La lista no está vacía
nuevoNodo->siguiente = ultimo->siguiente; // El nuevo nodo apunta al que era el primero
ultimo->siguiente = nuevoNodo; // El último nodo ahora apunta al nuevo primer nodo
// 'ultimo' sigue siendo el mismo nodo, pero el "inicio" conceptual ha cambiado.
}
printf("Elemento %d insertado al inicio.\n", dato);
return ultimo;
}
3. Mostrar la Lista (mostrarLista)
Recorrer y mostrar una lista circular requiere cuidado para no caer en un bucle infinito. Empezamos desde el nodo siguiente al ultimo (que es el primer nodo) y continuamos hasta que volvamos a él.
// Muestra los elementos de la lista circular
void mostrarLista(struct Nodo* ultimo) {
if (ultimo == NULL) {
printf("La lista está vacía.\n");
return;
}
struct Nodo* actual = ultimo->siguiente; // Empezamos por el "primer" nodo
printf("Lista: ");
do {
printf("%d -> ", actual->dato);
actual = actual->siguiente;
} while (actual != ultimo->siguiente); // Continuar hasta volver al inicio
printf("(vuelve a %d)\n", ultimo->siguiente->dato); // Indicar la circularidad
}
4. Eliminar un Elemento (eliminarElemento)
Eliminar un elemento es más complejo. Necesitamos encontrar el nodo a eliminar y el nodo anterior a él para reconectar la lista. Aquí consideraremos la eliminación de un nodo con un valor específico.
// Elimina un nodo con un valor específico de la lista circular
// Devuelve el puntero al (posiblemente nuevo) último nodo
struct Nodo* eliminarElemento(struct Nodo* ultimo, int valor) {
if (ultimo == NULL) {
printf("La lista está vacía, no se puede eliminar.\n");
return NULL;
}
struct Nodo* actual = ultimo->siguiente; // Nodo "cabeza" o primer nodo
struct Nodo* anterior = ultimo; // Nodo anterior al 'actual'
// Caso especial: ¿El único nodo es el que queremos eliminar?
if (actual == ultimo && actual->dato == valor) {
printf("Elemento %d eliminado (era el único).\n", valor);
free(actual);
return NULL; // La lista queda vacía
}
// Recorrer la lista para encontrar el nodo
do {
if (actual->dato == valor) {
// Encontrado el nodo a eliminar
anterior->siguiente = actual->siguiente; // El anterior salta al siguiente del actual
// Si el nodo a eliminar era el 'ultimo', actualizamos 'ultimo'
if (actual == ultimo) {
ultimo = anterior;
}
// Si el nodo a eliminar era el único que quedaba después de que 'ultimo' se actualizara
// (esto ocurre si eliminamos el 'ultimo' y solo quedaba un nodo que era el 'primero')
// o si la lista se vacía porque 'anterior' ahora es igual a 'actual->siguiente'
// y ese era el único nodo.
if (anterior == actual->siguiente && anterior->dato == valor) { // Este caso es complejo y puede simplificarse
// si se maneja el caso de un solo nodo de forma más robusta.
// Una mejor comprobación sería si anterior->siguiente == anterior
// después de la eliminación, indicando que solo queda un nodo.
// O si 'ultimo' se vuelve igual a 'ultimo->siguiente'
// y ese es el nodo a eliminar.
// Este bloque necesita una revisión cuidadosa para el caso de un solo nodo restante
// o la lista vaciándose. La lógica de arriba para el único nodo ya cubre un caso.
// Si después de eliminar, anterior->siguiente es el mismo anterior,
// y ese es el que se eliminó, la lista podría quedar mal.
// La condición `actual == ultimo` ya actualiza `ultimo`.
// Si `anterior` se convierte en el nuevo `ultimo` y era el único nodo,
// `ultimo->siguiente` debe ser `ultimo`.
}
printf("Elemento %d eliminado.\n", valor);
free(actual);
return ultimo; // Devolvemos el (posiblemente actualizado) último nodo
}
anterior = actual;
actual = actual->siguiente;
} while (actual != ultimo->siguiente); // Recorrer hasta volver al inicio
printf("Elemento %d no encontrado en la lista.\n", valor);
return ultimo; // No se encontró, la lista no cambia
}
Nota sobre eliminarElemento: La lógica de eliminación, especialmente los casos borde (lista vacía, un solo elemento, eliminar el ultimo nodo), puede ser delicada en listas circulares. La implementación anterior es un punto de partida y podría requerir pruebas exhaustivas y refinamientos para cubrir todos los escenarios perfectamente, especialmente si la lista se vacía o queda con un solo nodo. Una estrategia común es tener un nodo «cabeza» ficticio (dummy head) para simplificar estos casos, pero eso añade otra capa.
5. Buscar un Elemento (buscarElemento)
Similar a mostrar, pero retornamos si el elemento fue encontrado.
// Busca un elemento en la lista. Devuelve 1 si se encuentra, 0 si no.
int buscarElemento(struct Nodo* ultimo, int valor) {
if (ultimo == NULL) {
return 0; // Lista vacía
}
struct Nodo* actual = ultimo->siguiente; // Empezar por el primer nodo
do {
if (actual->dato == valor) {
return 1; // Encontrado
}
actual = actual->siguiente;
} while (actual != ultimo->siguiente);
return 0; // No encontrado
}
Liberando la Memoria (liberarLista)
Es crucial liberar toda la memoria asignada dinámicamente cuando ya no necesitemos la lista para evitar fugas de memoria.
// Libera toda la memoria asignada a los nodos de la lista circular
// Devuelve NULL ya que la lista ya no existe.
struct Nodo* liberarLista(struct Nodo* ultimo) {
if (ultimo == NULL) {
return NULL; // Nada que liberar
}
struct Nodo* actual = ultimo->siguiente; // Empezar por el primer nodo
struct Nodo* siguienteNodo;
// Romper el ciclo para evitar bucle infinito al liberar
ultimo->siguiente = NULL;
while (actual != NULL) {
siguienteNodo = actual->siguiente;
// printf("Liberando nodo con dato: %d\n", actual->dato); // Para depuración
free(actual);
actual = siguienteNodo;
}
printf("Toda la memoria de la lista ha sido liberada.\n");
return NULL; // La lista ya no existe
}
Ejemplo Completo y Uso (main)
Pongamos todo junto para ver nuestra lista circular en acción.
#include <stdio.h>
#include <stdlib.h>
// Definición de la estructura Nodo
struct Nodo {
int dato;
struct Nodo* siguiente;
};
// --- Prototipos de las funciones ---
struct Nodo* crearNodo(int dato);
struct Nodo* insertarAlFinal(struct Nodo* ultimo, int dato);
struct Nodo* insertarAlInicio(struct Nodo* ultimo, int dato);
void mostrarLista(struct Nodo* ultimo);
struct Nodo* eliminarElemento(struct Nodo* ultimo, int valor); // Prototipo actualizado
int buscarElemento(struct Nodo* ultimo, int valor);
struct Nodo* liberarLista(struct Nodo* ultimo);
// --- Función Principal (main) ---
int main() {
struct Nodo* miListaCircular = NULL; // Inicialmente la lista está vacía
printf("--- Insertando elementos ---\n");
miListaCircular = insertarAlFinal(miListaCircular, 10); // Lista: 10 -> (10)
mostrarLista(miListaCircular);
miListaCircular = insertarAlFinal(miListaCircular, 20); // Lista: 10 -> 20 -> (10)
mostrarLista(miListaCircular);
miListaCircular = insertarAlInicio(miListaCircular, 5); // Lista: 5 -> 10 -> 20 -> (5)
mostrarLista(miListaCircular);
miListaCircular = insertarAlFinal(miListaCircular, 30); // Lista: 5 -> 10 -> 20 -> 30 -> (5)
mostrarLista(miListaCircular);
printf("\n--- Buscando elementos ---\n");
int val1 = 20;
int val2 = 99;
printf("¿Se encuentra el %d? %s\n", val1, buscarElemento(miListaCircular, val1) ? "Sí" : "No");
printf("¿Se encuentra el %d? %s\n", val2, buscarElemento(miListaCircular, val2) ? "Sí" : "No");
printf("\n--- Eliminando elementos ---\n");
miListaCircular = eliminarElemento(miListaCircular, 10); // Lista: 5 -> 20 -> 30 -> (5)
mostrarLista(miListaCircular);
miListaCircular = eliminarElemento(miListaCircular, 5); // Lista: 20 -> 30 -> (20) (elimina el "primero")
mostrarLista(miListaCircular);
miListaCircular = eliminarElemento(miListaCircular, 30); // Lista: 20 -> (20) (elimina el "ultimo")
mostrarLista(miListaCircular);
miListaCircular = eliminarElemento(miListaCircular, 20); // Lista vacía (elimina el único que queda)
mostrarLista(miListaCircular);
miListaCircular = eliminarElemento(miListaCircular, 100); // Intento de eliminar en lista vacía
mostrarLista(miListaCircular);
printf("\n--- Re-poblando y liberando la lista ---\n");
miListaCircular = insertarAlFinal(miListaCircular, 100);
miListaCircular = insertarAlFinal(miListaCircular, 200);
mostrarLista(miListaCircular);
miListaCircular = liberarLista(miListaCircular);
mostrarLista(miListaCircular); // Debería decir que está vacía
return 0;
}
// --- Definiciones de las funciones ---
// (Aquí irían las definiciones de crearNodo, insertarAlFinal, etc.,
// que ya hemos visto arriba. Por brevedad, no las repetiré aquí, pero en un archivo .c
// completo, estarían aquí o antes de main si no se usan prototipos.)
struct Nodo* crearNodo(int dato) {
struct Nodo* nuevoNodo = (struct Nodo*)malloc(sizeof(struct Nodo));
if (nuevoNodo == NULL) {
perror("Error: No se pudo asignar memoria para el nuevo nodo");
return NULL;
}
nuevoNodo->dato = dato;
nuevoNodo->siguiente = NULL;
return nuevoNodo;
}
struct Nodo* insertarAlFinal(struct Nodo* ultimo, int dato) {
struct Nodo* nuevoNodo = crearNodo(dato);
if (nuevoNodo == NULL) {
return ultimo;
}
if (ultimo == NULL) {
ultimo = nuevoNodo;
ultimo->siguiente = ultimo;
} else {
nuevoNodo->siguiente = ultimo->siguiente;
ultimo->siguiente = nuevoNodo;
ultimo = nuevoNodo;
}
// printf("Elemento %d insertado al final.\n", dato); // Movido a main o quitar para limpieza
return ultimo;
}
struct Nodo* insertarAlInicio(struct Nodo* ultimo, int dato) {
struct Nodo* nuevoNodo = crearNodo(dato);
if (nuevoNodo == NULL) {
return ultimo;
}
if (ultimo == NULL) {
ultimo = nuevoNodo;
ultimo->siguiente = ultimo;
} else {
nuevoNodo->siguiente = ultimo->siguiente;
ultimo->siguiente = nuevoNodo;
// 'ultimo' no cambia, solo el "inicio" conceptual
}
// printf("Elemento %d insertado al inicio.\n", dato); // Movido a main o quitar
return ultimo;
}
void mostrarLista(struct Nodo* ultimo) {
if (ultimo == NULL) {
printf("Lista: [Vacía]\n");
return;
}
struct Nodo* actual = ultimo->siguiente;
printf("Lista: ");
do {
printf("%d", actual->dato);
actual = actual->siguiente;
if (actual != ultimo->siguiente) {
printf(" -> ");
}
} while (actual != ultimo->siguiente);
printf(" -> (vuelve a %d)\n", ultimo->siguiente->dato);
}
// Implementación de eliminarElemento (simplificada y corregida para casos borde)
struct Nodo* eliminarElemento(struct Nodo* ultimo, int valor) {
if (ultimo == NULL) {
// printf("La lista está vacía, no se puede eliminar %d.\n", valor); // Mensaje opcional
return NULL;
}
struct Nodo* actual = ultimo->siguiente; // El "primer" nodo
struct Nodo* anterior = ultimo;
// Búsqueda del nodo a eliminar
do {
if (actual->dato == valor) {
// Nodo encontrado
if (actual == ultimo && actual->siguiente == actual) { // Único nodo en la lista
free(actual);
printf("Elemento %d eliminado (era el único).\n", valor);
return NULL; // La lista queda vacía
}
anterior->siguiente = actual->siguiente; // Re-enlazar
if (actual == ultimo) { // Si eliminamos el nodo 'ultimo'
ultimo = anterior; // El anterior se convierte en el nuevo 'ultimo'
}
// Si el 'actual' era el 'primero' (ultimo->siguiente) y se eliminó,
// no es necesario hacer nada más con 'ultimo' si no era el único nodo,
// ya que 'ultimo->siguiente' ya apunta al nuevo 'primero'.
free(actual);
printf("Elemento %d eliminado.\n", valor);
return ultimo;
}
anterior = actual;
actual = actual->siguiente;
} while (actual != ultimo->siguiente && anterior != ultimo); // Condición de bucle ajustada
// Si el bucle termina porque actual == ultimo->siguiente, pero no se encontró
// (esto podría pasar si el valor no está y solo hay un elemento, o si el valor
// es el del último nodo y el bucle no lo procesó correctamente).
// Se necesita una comprobación final para el último nodo si el bucle no lo cubrió.
if (ultimo->siguiente->dato == valor && actual == ultimo->siguiente && anterior == ultimo) { // Caso donde el valor está en el único nodo o el primer nodo y el bucle no lo manejó
// Este caso debería ser cubierto por la lógica anterior si hay más de un nodo.
// Si es el último nodo (que también es el primero en una lista de un solo elemento)
if (ultimo->dato == valor && ultimo->siguiente == ultimo) { // Único nodo
free(ultimo);
printf("Elemento %d eliminado (era el único).\n", valor);
return NULL;
} else if (ultimo->dato == valor) { // Si el valor a eliminar es el del nodo 'ultimo' (y hay más de un nodo)
// Este caso es más complejo y la lógica actual de 'actual == ultimo' debería manejarlo
// si 'actual' llega a ser 'ultimo'.
// La lógica actual de buscar hasta 'ultimo->siguiente' y actualizar 'ultimo' si 'actual == ultimo'
// debería ser suficiente. No se necesita este 'else if' si la lógica del bucle es correcta.
}
}
printf("Elemento %d no encontrado en la lista.\n", valor);
return ultimo;
}
int buscarElemento(struct Nodo* ultimo, int valor) {
if (ultimo == NULL) {
return 0;
}
struct Nodo* actual = ultimo->siguiente;
do {
if (actual->dato == valor) {
return 1;
}
actual = actual->siguiente;
} while (actual != ultimo->siguiente);
return 0;
}
struct Nodo* liberarLista(struct Nodo* ultimo) {
if (ultimo == NULL) {
return NULL;
}
struct Nodo* actual = ultimo->siguiente;
struct Nodo* proximoNodo;
ultimo->siguiente = NULL; // Romper el ciclo
while (actual != NULL) {
proximoNodo = actual->siguiente;
free(actual);
actual = proximoNodo;
}
// printf("Toda la memoria de la lista ha sido liberada.\n"); // Mensaje opcional
return NULL;
}
Para compilar y ejecutar:
- Guarda el código anterior como un archivo (por ejemplo,
lista_circular.c). - Compila usando un compilador de C como GCC:
gcc lista_circular.c -o programa_lista - Ejecuta:
./programa_lista(en Linux/macOS) oprograma_lista.exe(en Windows).
Conclusión
Las listas circulares simplemente enlazadas son una estructura de datos versátil con aplicaciones interesantes. Aunque su manejo, especialmente en operaciones de eliminación y recorrido, requiere atención al detalle para evitar errores comunes como bucles infinitos o punteros incorrectos, ofrecen una forma elegante de representar datos enlazados en un ciclo continuo.
Dominar las listas enlazadas en C te proporciona una base sólida para entender estructuras más complejas y para tomar decisiones informadas sobre qué estructura de datos es la más adecuada para tus proyectos.
¡No dudes en experimentar con este código y expandirlo! Por ejemplo, podrías intentar implementar insertar nodos en una posición específica o eliminar el primer elemento de forma más directa.
Deja una respuesta