wake-up-neo.net

Warum brauchen wir genau eine "Circular Linked List" (einfach oder doppelt) Datenstruktur?

Warum brauchen wir genau eine "Circular Linked List" (einfach oder doppelt) Datenstruktur?

Welches Problem löst es, das bei einfachen verknüpften Listen (einzeln oder doppelt) offensichtlich ist? 

35
user366312

Ein einfaches Beispiel zeigt, wer an der Reihe ist, in einem Multiplayer-Brettspiel. Alle Spieler in eine zirkuläre verknüpfte Liste setzen. Nachdem ein Spieler an der Reihe ist, geht man zum nächsten Spieler in der Liste über. Dies bewirkt, dass das Programm unter den Spielern unbegrenzt läuft.

Um eine kreisförmige verknüpfte Liste zu durchlaufen, speichern Sie einen Zeiger auf das erste Element, das Sie sehen. Wenn Sie dieses Element wieder sehen, haben Sie die gesamte Liste durchlaufen.

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

Zwei Gründe, um sie zu verwenden:

1) Einige Problembereiche sind von Natur aus kreisförmig. 

Zum Beispiel können die Quadrate auf einer Monopoly-Tafel in einer zirkular verknüpften Liste dargestellt werden, um deren inhärente Struktur abzubilden.

2) Einige Lösungen können aus Gründen der Effizienz einer zirkular verknüpften Liste zugeordnet werden.

Ein Jitter-Puffer ist beispielsweise eine Art Puffer, der nummerierte Pakete aus einem Netzwerk entnimmt und sortiert, sodass ein Video- oder Audioplayer sie z. Pakete, die zu langsam (laggy) sind, werden verworfen.

Dies kann in einem Umlaufpuffer dargestellt werden, ohne dass ständig Speicher zugewiesen und freigegeben werden muss, da die Slots nach der Wiedergabe erneut verwendet werden können.

Könnte mit einer verknüpften Liste implementiert werden, es würde jedoch ständige Hinzufügungen und Löschungen der Liste geben, anstatt die Konstanten zu ersetzen (die billiger sind).

20
Oddthinking

Anwendungen

1) Wir können eine zirkuläre verknüpfte Liste für jede Anwendung verwenden, bei der die Einträge rotierend erscheinen.
2) Eine zirkular verknüpfte Liste ist die Grundidee des Round-Robin-Scheduling-Algorithmus.

Etwas habe ich von Google gefunden.

Eine einfach verknüpfte zirkuläre Liste ist eine verknüpfte Liste, bei der der letzte Knoten in der Liste auf den ersten Knoten in der Liste zeigt. Eine zirkuläre Liste enthält keine NULL-Zeiger. 

Ein gutes Beispiel für eine Anwendung, bei der eine umlaufende verknüpfte Liste verwendet werden sollte, ist ein Timesharing-Problem, das vom Betriebssystem gelöst wird. 

In einer Timesharing-Umgebung muss das Betriebssystem eine Liste der aktuellen Benutzer verwalten und jedem Benutzer alternativ die Verwendung eines kleinen Teils der CPU-Zeit für jeden Benutzer ermöglichen. Das Betriebssystem wählt einen Benutzer aus, lässt ihn eine kleine CPU-Zeit verwenden und wechselt dann zum nächsten Benutzer usw. 

Für diese Anwendung sollten keine NULL-Zeiger vorhanden sein, es sei denn, es ist absolut niemand vorhanden, der die CPU-Zeit anfordert.

8
Praveen S

Eine zirkulare verknüpfte Liste kann effektiv zum Erstellen einer Warteschlange (FIFO) oder einer Deque (effizientes Einfügen und Entfernen von vorne und hinten) verwendet werden. Siehe http://en.wikipedia.org/wiki/Linked_list#Circularlylinked_vs._linearlylinked

5
amit

Ein gutes Beispiel für eine Anwendung, bei der eine umlaufende verknüpfte Liste verwendet werden sollte, ist ein Timesharing-Problem, das vom Betriebssystem gelöst wird.

1
Rahul Singal

Zirkulär verknüpfte Listen werden häufig in Anwendungen verwendet, in denen Aufgaben wiederholt werden müssen, oder in zeitlich verteilten Anwendungen. Die zirkuläre Warteschlange kann die durchgeführten Aufgaben nachverfolgen, die ausgeführt werden müssen. Sobald die bestimmte Aufgabe erledigt ist, springt sie zur nächsten, und wenn der gesamte Satz von Aufgaben abgeschlossen ist, springt er wieder zur ersten Aufgabe, um den verbleibenden Job abzuschließen. Im praktischen Einsatz: Wenn Sie mehrere Anwendungen auf Ihrem System öffnen, wird der Speicher dieser Anwendungen kreisförmig gespeichert. Sie können dies beobachten, wenn u ständig Win + Tab/Alt + Tab zum Wechseln zwischen Anwendungen drückt In Multiplayer-Brettspielen wird jedem Spieler ein Knoten in der verknüpften Liste zugewiesen, und die Rotation wird ausgeführt 

0
wolf_flow

Wir können eine kreisförmig verknüpfte Liste beim Ressourcen-Pooling verwenden. Wenn viele Benutzer eine gemeinsam genutzte Ressource verwenden möchten, können wir diese Ressource mithilfe einer kreisförmig verknüpften Liste zuordnen.

0
Nitish Goyal

Eine zirkuläre Liste ist einfacher als eine normale doppelt verknüpfte Liste. Anhängen ist nur vorangestellt und einmal nach vorne schieben, Pop zurück ist nur einmal zurückschieben und Pop vorne Wenn Sie die beiden Enden miteinander verbinden, erhalten Sie eine doppelte Liste für die Kosten der Implementierung der Operationen einer einseitigen Liste.

0
u0b34a0f6ae

Zirkulär verknüpfte Listen (einzeln oder doppelt) sind nützlich für Anwendungen, die jeden Knoten gleichermaßen besuchen müssen nd die Listen könnten wachsen. Wenn die Größe der Liste festgelegt ist, ist die Verwendung der kreisförmigen Warteschlange (Geschwindigkeit und Speicher) wesentlich effizienter.

0
yoonghm