Las listas enlazadas, también denominadas listas simplemente enlazadas, son sumamente útiles y convenientes para diferentes usos y aplicaciones; algunas de las cuales ya han sido mencionadas. Aunque las listas simplemente enlazadas son muy dinámicas presentan, como casi todo en la vida, ciertos inconvenientes.
Algunas de las situaciones indeseables que se tienen con una lista simplemente enlazada son las siguientes:
Algunas de las situaciones indeseables que se tienen con una lista simplemente enlazada son las siguientes:
- Dada una única referencia a un nodo determinado de la lista enlazada y suponiendo que éste no sea el primero, no se puede llegar a ninguno de los nodos que lo preceden, es decir, no pueden alcanzarse los nodos anteriores a él.
- Si por alguna razón se recorre la lista enlazada, siempre debe conservarse una referencia externa (además de la que se utilizó para el recorrido) al inicio de dicha lista enlazada con la finalidad de poder volver a recorrer la lista nuevamente en caso de ser necesario.
Con base en lo anterior, considere la siguiente modificación respecto a la estructura de una lista simplemente enlazada:
El elemento siguiente en el último nodo hará referencia al primer nodo y no a null; siendo en esto diferente a lo que se define para una lista simplemente enlazada convencional.
Al tipo de lista enlazada que adopta dicha modificación se le denomina lista simplemente enlazada circular. Su representación se muestra en la siguiente figura:
 |
| Abstracción de una lista simplemente enlazada circular representada como una secuencia de nodos. |
Es importante hacer notar que en una lista enlazada circular es posible llegar a cualquier otro nodo de la estructura de datos partiendo de un nodo distinto cualquiera, lo cual subsana los dos inconvenientes enunciados al principio de esta sección para una lista simplemente enlazada.
Observe también que una lista enlazada circular no tiene un “primer” o “último” nodo natural, por lo que se debe establecer un primer y último nodo por convención, lo cual es más una conveniencia que una característica inherente a la estructura de datos.
Finalmente, tome en cuenta que una referencia a null/nullptr (Java/C++) representa una lista circular vacía, y que una lista circular de un solo nodo es un nodo cuyo atributo de auto referencia contiene una referencia hacia sí mismo como lo muestra la siguiente figura:
Observe también que una lista enlazada circular no tiene un “primer” o “último” nodo natural, por lo que se debe establecer un primer y último nodo por convención, lo cual es más una conveniencia que una característica inherente a la estructura de datos.
Finalmente, tome en cuenta que una referencia a null/nullptr (Java/C++) representa una lista circular vacía, y que una lista circular de un solo nodo es un nodo cuyo atributo de auto referencia contiene una referencia hacia sí mismo como lo muestra la siguiente figura:
 |
| Lista circular de un solo elemento. |
El problema de Josephus.
El siguiente es un problema clásico en el área de las estructuras de datos, y su solución utilizando listas enlazadas circulares es una aplicación clave:
Un grupo de soldados se encuentra rodeado por una abrumadora fuerza enemiga. No hay esperanza de victoria sin refuerzos. Lamentablemente, sólo hay un caballo disponible para ir en su busca (o escapar).
Los soldados realizan un pacto de honor para determinar cuál de ellos tomará el caballo y, en el mejor de los casos, pedirá ayuda. Para ello, forman un círculo y van eligiendo un número de un sombrero (n). También se elige uno de los nombres de los soldados de otro sombrero.
Iniciando con el soldado cuyo nombre se eligió, se empieza a contar en el sentido de las manecillas del reloj alrededor del círculo. Cuando la cuenta llega a n el soldado correspondiente se retira del círculo y la cuenta vuelve a empezar con el soldado que se encontraba a su derecha.
El proceso continúa análogamente hasta que sólo queda un soldado, mismo que tomará al caballo y pedirá ayuda (o escapará trágica e irremediablemente para los demás soldados).
- El orden en el cual se eliminan los soldados del círculo.
- Cuál soldado es el que escapa.
