¿Por qué es exactamente lo que necesitamos una “lista enlazada circular” (simple o doble) estructura de datos?

StackOverflow https://stackoverflow.com/questions/3589772

Pregunta

¿Por qué es exactamente lo que necesitamos una "lista enlazada circular" (simple o doble) estructura de datos?

¿Qué problema soluciona esto es evidente con listas simples Vinculado (simple o doble)?

¿Fue útil?

Solución

Un ejemplo sencillo es hacer el seguimiento de quién es el turno en un juego de mesa multi-jugador. Poner todos los jugadores en una lista enlazada circular. Después de un jugador toma su turno, avanzar al siguiente jugador en la lista. Esto hará que el programa para el ciclo indefinidamente entre los jugadores.

Para recorrer una lista enlazada circular, almacenar un puntero al primer elemento que se ve. Cuando ves a ese elemento nuevo, que ha atravesado toda la lista. 

void traverse(CircularList *c) {
  CircularList start = c;
  do {
    operateOnNode(c);
    c = c->next;
  } while(c != start);
}

Otros consejos

Dos razones para utilizarlos:

1) Algunos dominios de problemas son inherentemente circular.

Por ejemplo, los cuadrados de un tablero de Monopoly se puede representar en una lista circular ligada, para mapear a su estructura inherente.

2) Algunas soluciones se puede asignar a una lista circularmente vinculado para la eficiencia.

Por ejemplo, un búfer de fluctuación es un tipo de memoria intermedia que lleva los paquetes numerados de una red y los coloca en orden, para que (por ejemplo) un vídeo o reproductor de audio se pueden reproducir en orden. Los paquetes que son demasiado lento (lag) se descartan.

Esto se puede representar en un buffer circular, sin necesidad de asignar y liberar memoria constantemente, como ranuras se pueden volver a utilizar una vez que se han jugado.

podría implementarse con una lista vinculada, pero no habría constantes adiciones y supresiones a la lista, en lugar de sustitución a las constantes (que son más baratos).

Aplicaciones

1) Podemos utilizar lista enlazada circular cualquier aplicación en la que aparecen las entradas de manera rotativa.
2) lista enlazada circular es la idea básica del algoritmo robin ronda.

Algo que encontré de Google.

  

Una lista circular de enlace simple es una lista enlazada, donde el último nodo en theList puntos al primer nodo en la lista. Una lista circular no contiene punteros NULL.

     

Un ejemplo bien de una aplicación en la lista enlazada circular debe utilizarse 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 presentes y debe permitir alternativamente cada usuario utilizar una pequeña porción de tiempo de CPU, un usuario a la vez. El sistema operativo escogerá un usuario, dejarlo / a usar una pequeña cantidad de tiempo de CPU y luego pasar al siguiente usuario, etc.

     

Para esta aplicación, no debe haber punteros NULL si no hay absolutamente nadie que solicita tiempo de CPU.

una lista enlazada circular se puede utilizar eficazmente para crear una cola (FIFO) o un deque (inserto eficiente y retirar del frente y parte posterior). Ver http://en.wikipedia.org/wiki/Linked_list#Circularly- linked_vs._linearly ligado

Un buen ejemplo de una aplicación en la lista enlazada circular debe utilizarse es un problema de tiempo compartido resuelto por el sistema operativo.

Una lista circular es más simple que una lista doblemente enlazada normales. Anexar es sólo anteponer y el desplazamiento hacia adelante una vez, POP volver se acaba de cambiar de nuevo una vez y delante pop . La vinculación de los dos extremos juntos, se obtiene una lista de doble extremo para el costo de sólo la aplicación de las operaciones de una lista terminado una sola.

Podemos usar lista enlazada circular en la puesta en común de recursos. Si muchos usuarios desean utilizar un recurso compartido, podemos asignar ese recurso mediante lista enlazada circular.

listas enlazadas circulares son ampliamente utilizados en aplicaciones en las tareas han de repetirse o en aplicaciones de tiempo compartido. cola circular puede mantener un seguimiento de las tareas que se han realizado y que tiene que realizar, una vez que la tarea específica se realiza salta al siguiente y cuando se conpleted todo el conjunto de la tarea de nuevo salta a la primera tarea para completar el trabajo restante. En el uso práctico: al abrir varias aplicaciones en el sistema de la memoria de esas aplicaciones se guardan en forma circular, se puede observar esto si u oprima continuamente ganar + tab / ALT + TAB para cambiar de aplicación. También en multijugador juegos de mesa, cada jugador se le asigna al nodo de la lista enlazada y se realiza la rotación

Circular vinculado listas (simple o doble) son útiles para aplicaciones que necesidad de visitar cada nodo igualmente y las listas podrían crecer. Si el tamaño de la lista si es fija, es mucho más eficiente (la velocidad y la memoria) para utilizar cola circular.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top