Eine verknüpfte Liste ist eine lineare Datenstruktur, in der die Elemente in Knoten gespeichert sind. Jeder Knoten enthält ein Datenfeld und einen Verweis auf den nächsten Knoten in der Liste. Der letzte Knoten in der Liste hat einen Verweis auf null.
Eine zirkulär verknüpfte Liste ist eine verknüpfte Liste, bei der der letzte Knoten mit dem ersten Knoten verknüpft ist und eine kreisförmige Struktur bildet. Dies bedeutet, dass es in einer zirkulär verknüpften Liste keinen Nullverweis gibt.
Hier ist eine Darstellung einer zirkulären verknüpften Liste:
„
Kopf -> Knoten1 -> Knoten2 -> Knoten3 -> Kopf
„
In dieser Darstellung zeigt der „Kopf“-Knoten auf den ersten Knoten in der Liste und der „Knoten3“-Knoten zeigt auf den „Kopf“-Knoten.
Zirkuläre verknüpfte Listen werden häufig verwendet, wenn die Liste mehrmals durchlaufen werden muss. Dies liegt daran, dass die Position des aktuellen Knotens in der Liste nicht im Auge behalten werden muss. Wenn das Ende der Liste erreicht ist, kann die Durchquerung einfach vom ersten Knoten aus fortgesetzt werden.
Ein weiterer Vorteil zirkulär verknüpfter Listen besteht darin, dass sie zur Implementierung von Warteschlangen und Stapeln verwendet werden können. Warteschlangen sind Datenstrukturen, in denen Elemente an einem Ende hinzugefügt und am anderen Ende entfernt werden, während Stapel Datenstrukturen sind, in denen Elemente am selben Ende hinzugefügt und von diesem entfernt werden.
Zirkuläre verknüpfte Listen werden nicht so häufig verwendet wie herkömmliche verknüpfte Listen, bieten jedoch in bestimmten Situationen einige Vorteile.
