Estructura de datos - Lista circular
La lista circular es una variante de la estructura de lista enlazada. Su característica principal es que el último nodo de la lista ya no apunta a NULL, sino que vuelve a apuntar al primer nodo, por lo que toda la lista forma lógicamente una estructura en anillo.
Características estructurales de la lista circular
Lista circular simplemente enlazada
Lista circular doblemente enlazada
Lista normal: next al final = NULL; la condición de terminación del recorrido es cur == NULL.
Lista circular: next al final = head; la condición de terminación del recorrido es cur == head (volver al punto de partida).
Operaciones comunes:Insertar nodo cabeza O(n) — hay que encontrar primero el nodo cola | El recorrido usa un bucle do...while.
Insertar nodo cola O(1) (manteniendo el puntero tail) | La eliminación es similar.
Las listas circulares se dividen principalmente en dos tipos:
- Lista circular simplemente enlazada: cada nodo solo guarda un puntero next; el next del último nodo vuelve a apuntar al nodo cabeza.
- Lista circular doblemente enlazada: sobre la base de una lista doblemente enlazada, el next del último nodo apunta al nodo cabeza, y el prev del nodo cabeza apunta al último nodo.
La característica más destacada de la lista circular es que admite de forma natural un recorrido continuo donde el final se conecta con el principio.
La condición para determinar el final del recorrido no es "si se ha llegado a NULL", sino "si se ha vuelto al nodo inicial".
Operaciones básicas
Ejemplo
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* Crear un nuevo nodo */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; /* Cuando hay un solo nodo, next apunta a sí mismo, formando un anillo */
return newNode;
}
/* Insertar un nodo en la cabeza de la lista circular
Complejidad temporal: O(n) — hay que encontrar primero el nodo cola para actualizar su puntero next */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode; /* Lista vacía, el nuevo nodo forma un anillo por sí solo */
}
/* Encontrar el nodo cola (es decir, el nodo cuyo next apunta a head) */
struct Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
newNode->next = head; /* El next del nuevo nodo apunta al nodo cabeza original */
tail->next = newNode; /* El next del nodo cola apunta al nuevo nodo (nueva cabeza) */
return newNode; /* El nuevo nodo se convierte en la nueva cabeza */
}
/* Recorrer la lista circular (una vuelta)
Comenzando desde el nodo cabeza, detenerse cuando se vuelva a la cabeza */
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* cur = head;
printf("Lista circular: ");
do {
printf("%d -> ", cur->data);
cur = cur->next;
} while (cur != head); /* Terminar al volver al punto de partida */
printf((volver al punto de partida)\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverse(head);
/* Salida: Lista circular: 10 -> 20 -> 30 -> (volver al punto de partida) */
return 0;
}
La clave del recorrido de la lista circular es usar
do...whilela sentencia en lugar dewhile. Debido a que al usarwhile (cur != head)cuando el estado inicial cur es igual a head, el bucle no se ejecutará en absoluto. Perodo...whilegarantiza que el cuerpo del bucle se ejecute al menos una vez, y luego se verifica la condición de terminación.
Aplicación clásica: el problema de Josephus
Orden de eliminación y resultado final (n=7, m=3)
El problema de Josephus (Josephus Problem)es un problema matemático clásico:
Supongamos que n personas forman un círculo. Comenzando desde la primera persona, se cuenta; cada vez que se llega a la m-ésima persona, esta es eliminada del círculo, y luego el conteo comienza de nuevo desde la siguiente persona. Este proceso se repite hasta que solo queda una persona.
Este problema encaja de forma natural con la característica estructural de la lista circular de "conectar el final con el principio y acceso cíclico".
Ejemplo
#include <stdlib.h>
struct Node {
int data; /* Número de persona */
struct Node* next;
};
/* Resolución del problema de Josephus
Parámetros: n número total de personas, m la persona que se cuente hasta m sale del círculo
Usar una lista circular para simular todo el proceso */
void josephus(int n, int m) {
if (n <= 0) return;
/* Paso 1: crear una lista circular con n personas (numeradas de 1 a n) */
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = head; /* Cuando solo hay una persona, formando un anillo */
struct Node* tail = head;
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = head; /* El next del nuevo nodo apunta siempre a la cabeza */
tail->next = newNode; /* El next del nodo anterior apunta al nuevo nodo */
tail = newNode; /* tail se desplaza */
}
/* Paso 2: simular el proceso de eliminación */
struct Node* cur = head;
struct Node* prev = tail; /* prev apunta al predecesor de cur, inicialmente al nodo cola */
printf("Problema de Josephus (n=%d, m=%d) orden de eliminación: ", n, m);
while (cur->next != cur) { /* Terminar cuando solo quede un nodo (anillo) */
/* Contar: contar m-1 veces, haciendo avanzar a prev y cur simultáneamente */
for (int count = 1; count < m; count++) {
prev = cur;
cur = cur->next;
}
/* Al contar hasta m, cur es eliminado */
printf("%d ", cur->data);
prev->next = cur->next; /* Saltar cur */
free(cur); /* Liberar el nodo eliminado */
cur = prev->next; /* Volver a contar desde la siguiente persona */
}
printf("=> Superviviente final: %d"\n", cur->data); /* Mostrar la última persona */
free(cur);
}
int main() {
josephus(7, 3);
/* Salida: Problema de Josephus (n=7, m=3) orden de eliminación: 3 6 2 7 5 1 => Superviviente final: 4 */
return 0;
}
Otros escenarios de aplicación
| Escenario | Descripción |
|---|---|
| Programación por turnos de tiempo en sistemas operativos | La CPU asigna por turnos un intervalo de tiempo a cada proceso; cuando un proceso agota su intervalo, le toca al siguiente, formando un ciclo. |
| Juegos multijugador por turnos para jugar cartas | En juegos de cartas y tablero, los jugadores actúan por turnos en sentido horario (o antihorario). |
| Búfer circular | Búfer circular para flujos de datos de audio/vídeo; cuando se llena, vuelve al principio y sobrescribe los datos antiguos. |