GUÍA 14-10-26 Estructuras de Datos

CN122 · miércoles 14/10/2026 · 13:00-14:15 · Sesión 19

Taller de listas circulares · Comparación de variantes

CONSOLIDACIÓN

Sesión de práctica sobre listas circulares y comparación con las variantes vistas.

CASOS FRONTERA QUE HAY QUE MANEJAR

• Lista vacía: el apuntador externo es NULL.
• Un solo nodo: apunta a sí mismo; al eliminarlo hay que poner el externo en NULL.
• Eliminar el nodo al que apunta el externo: hay que reubicarlo antes de liberar.

JOSEFO PASO A PASO

1. Formar la lista circular con n personas.

2. Avanzar k−1 nodos desde la posición actual.

3. Eliminar el siguiente y continuar desde ahí.

4. Repetir hasta que quede uno solo.

ROUND-ROBIN

Simular un planificador donde cada proceso recibe un quantum fijo. Si termina, se elimina de la lista; si no, se pasa al siguiente. La lista circular hace la simulación casi trivial, que es la razón de usarla.

COMPARATIVA DE LO VISTO

• Simple — mínima memoria; solo hacia adelante; sin acceso al anterior.
• Circular — recorrido cíclico natural; ambos extremos en O(1) si el externo apunta al último.
• Doblemente ligada — recorrido en ambos sentidos; un apuntador extra por nodo.

PRÁCTICA

Terminar Josefo y la simulación round-robin, y medir el consumo de memoria de cada variante.