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

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

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

Ein einfaches Beispiel ist das Nachverfolgen, wer in einem Mehrspieler-Brettspiel an der Reihe ist. Setzen Sie alle Spieler in eine kreisförmige verknüpfte Liste. Nachdem ein Spieler an der Reihe ist, rückt zum nächsten Spieler in der Liste vor. Dadurch wird das Programm endlos zwischen den Spielern durchlaufen.

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

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

Zwei Gründe, sie zu verwenden:

1) Einige Problemdomänen sind von Natur aus kreisförmig.

Beispielsweise können die Quadrate auf einem Monopoly-Brett in einer kreisförmig verknüpften Liste dargestellt werden, um ihre inhärente Struktur abzubilden.

2) Einige Lösungen können aus Effizienzgründen auf eine kreisförmig verknüpfte Liste abgebildet werden.

Beispielsweise ist ein Jitter-Puffer eine Art Puffer, der nummerierte Pakete aus einem Netzwerk nimmt und sie in eine Reihenfolge bringt, sodass (beispielsweise) ein Video- oder Audioplayer sie der Reihe nach abspielen kann. Zu langsame (laggy) Pakete werden verworfen.

Dies kann in einem kreisförmigen Puffer dargestellt werden, ohne dass ständig Speicher zugewiesen und freigegeben werden muss, da Slots wiederverwendet werden können, sobald sie gespielt wurden.

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

Etwas, das ich von Google gefunden habe.

Eine einfach verknüpfte kreisförmige 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 zirkuläre verkettete Liste verwendet werden sollte, ist ein Timesharing-Problem, das vom Betriebssystem gelöst wird.

In einer Timesharing-Umgebung muss das Betriebssystem eine Liste der anwesenden Benutzer verwalten und jedem Benutzer abwechselnd erlauben, einen kleinen Teil der CPU-Zeit zu verwenden, jeweils einen Benutzer nach dem anderen. Das Betriebssystem wählt einen Benutzer aus, lässt ihn/sie ein wenig CPU-Zeit verwenden und geht dann zum nächsten Benutzer über usw.

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

Anwendungen

1) Wir können jede Anwendung mit kreisförmig verknüpften Listen verwenden, bei der die Einträge rotierend erscheinen.
2) Circular Linked List ist die Grundidee des Round-Robin-Scheduling-Algorithmus.

Eine zirkulär verknüpfte Liste kann effektiv verwendet werden, um eine Warteschlange (FIFO) oder eine Deque (effizientes Einfügen und Entfernen von vorne und hinten) zu erstellen. Sehen http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked

Zirkulär verknüpfte Listen werden häufig in Anwendungen verwendet, in denen Aufgaben wiederholt werden müssen, oder in Time-Sharing-Anwendungen. Die kreisförmige Warteschlange kann Aufgaben verfolgen, die ausgeführt wurden und die ausgeführt werden müssen. Sobald die bestimmte Aufgabe erledigt ist, springt sie zur nächsten und wenn der gesamte Aufgabensatz abgeschlossen ist, springt sie wieder zur ersten Aufgabe, um den verbleibenden Job abzuschließen. In der Praxis: Wenn Sie mehrere Anwendungen auf Ihrem System öffnen, wird der Speicher dieser Anwendungen kreisförmig gespeichert. Sie können dies beobachten, wenn Sie kontinuierlich Win+Tab/Alt+Tab drücken, um Anwendungen zu wechseln. Auch in Multiplayer-Brettspielen wird jedem Spieler ein Knoten in der verknüpften Liste zugewiesen, und die Rotation wird durchgeführt

Zirkulär verknüpfte Listen (einzeln oder doppelt) sind nützlich für Anwendungen, die jeden Knoten gleichermaßen besuchen müssen und die Listen könnten wachsen. Wenn die Größe der Liste festgelegt ist, ist es viel effizienter (Geschwindigkeit und Speicher), eine zirkuläre Warteschlange zu verwenden.