GUÍA 12-10-26 Estructuras de Datos

CN122 · lunes 12/10/2026 · 13:00-14:15 · Sesión 18

Listas circulares

LA ESTRUCTURA

Una lista circular no tiene NULL al final: el último nodo apunta al primero. Recorrerla requiere una condición de paro distinta, porque nunca se llega a NULL.

RECORRIDO CORRECTO

• do { … ; p = p->sig; } while (p != inicio);
• Con while normal el ciclo no ejecutaría nada si se compara antes de avanzar.

El error clásico es escribir un while que compara p != inicio desde el arranque: como p empieza siendo inicio, no entra nunca. Por eso se usa do-while.

APUNTAR AL ÚLTIMO, NO AL PRIMERO

Si el apuntador externo señala al último nodo, entonces ultimo->sig es el primero. Con un solo apuntador se accede a ambos extremos en O(1), lo que hace la inserción al inicio y al final igual de baratas.

OPERACIONES

• Insertar al inicio: enlazar tras el último y no mover el apuntador externo.
• Insertar al final: lo mismo, pero moviendo el apuntador externo al nuevo nodo.
• Eliminar: caso especial cuando queda un solo nodo, que apunta a sí mismo.

APLICACIONES

• Planificación round-robin: cada proceso recibe su turno y se regresa al primero.
• Listas de reproducción en repetición.
• Búferes circulares implementados con nodos.
• Problema de Josefo, el ejemplo clásico de eliminación cíclica.

RIESGO

Cualquier recorrido mal escrito produce un ciclo infinito en vez de un error. Conviene llevar un contador de seguridad mientras se depura.

PRÁCTICA

Implementar la lista circular con apuntador al último y resolver el problema de Josefo.