¿Por qué exactamente necesitamos una estructura de datos "Circular Linked List"(individual o doble)?
data-structures linked-list (8)
Algo que encontré de google
Una lista circular enlazada individualmente es una lista enlazada donde el último nodo en la lista apunta al primer nodo en la lista. Una lista circular no contiene punteros NULL.
Un buen ejemplo de una aplicación en la que se debe usar la lista circular vinculada es un problema de tiempo compartido resuelto por el sistema operativo.
En un entorno de tiempo compartido, el sistema operativo debe mantener una lista de usuarios actuales y debe permitir alternativamente que cada usuario use un pequeño segmento de tiempo de CPU, un usuario a la vez. El sistema operativo elegirá a un usuario, le permitirá usar una pequeña cantidad de tiempo de CPU y luego pasar al siguiente usuario, etc.
Para esta aplicación, no debería haber punteros nulos a menos que no haya absolutamente nadie que solicite tiempo de CPU.
¿Por qué exactamente necesitamos una estructura de datos "Circular Linked List" (individual o doble)?
¿Qué problema soluciona que es evidente con simples listas vinculadas (individual o doble)?
Aplicaciones
1) Podemos utilizar la lista circular vinculada a cualquier aplicación donde las entradas aparezcan de forma rotativa.
2) La lista circular vinculada es la idea básica del algoritmo de programación round robin.
Dos razones para usarlos:
1) Algunos dominios problemáticos son intrínsecamente circulares.
Por ejemplo, los cuadrados en un tablero de Monopoly se pueden representar en una lista circularmente vinculada, para mapear a su estructura inherente.
2) Algunas soluciones se pueden asignar a una lista de enlaces circulares para mayor eficiencia.
Por ejemplo, una memoria intermedia de fluctuación de fase es un tipo de memoria intermedia que toma paquetes numerados de una red y los coloca en orden, para que (por ejemplo) un reproductor de video o audio pueda reproducirlos en orden. Los paquetes que son demasiado lentos (laggy) se descartan.
Esto se puede representar en un búfer circular, sin necesidad de asignar y desasignar constantemente la memoria, ya que las ranuras se pueden reutilizar una vez que se han reproducido.
Podría implementarse con una lista enlazada, pero habría adiciones y eliminaciones constantes en la lista, en lugar de reemplazos a las constantes (que son más baratas).
Podemos usar una lista vinculada circularmente en la agrupación de recursos. Si muchos usuarios desean usar un recurso compartido, podemos asignar ese recurso mediante una lista con enlaces circulares.
Un buen ejemplo de una aplicación en la que se debe usar la lista circular vinculada es un problema de tiempo compartido resuelto por el sistema operativo.
Un ejemplo simple es hacer un seguimiento de a quién le toca el turno en un juego de mesa multijugador. Pon a todos los jugadores en una lista circular vinculada. Después de que un jugador toma su turno, avanza al siguiente jugador en la lista. Esto causará que el programa circule indefinidamente entre los jugadores.
Para recorrer una lista circular enlazada, almacena un puntero al primer elemento que veas. Cuando vuelves a ver ese elemento, has recorrido toda la lista.
void traverse(CircularList *c) {
CircularList start = c;
do {
operateOnNode(c);
c = c->next;
} while(c != start);
}
Una lista circular es más simple que una lista normal doblemente enlazada. Append es solo preceder y avanzar una vez, Pop back solo se desplaza hacia atrás una vez y emerge al frente . Al vincular los dos extremos, obtiene una lista de dos extremos por el costo de solo implementar las operaciones de una lista de un solo extremo.
Una lista circular vinculada se puede utilizar de manera efectiva para crear una cola (FIFO) o una deque (inserte de manera eficiente y elimínela de frente y atrás). Ver http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked