Datenstruktur - Zirkuläre verknüpfte Liste
Circular Linked List ist eine Variation der Linked List, bei der das erste Element auf das letzte Element und das letzte Element auf das erste Element zeigt. Sowohl die einfach verknüpfte Liste als auch die doppelt verknüpfte Liste können zu einer zirkulären verknüpften Liste erstellt werden.
Einfach verknüpfte Liste als Rundschreiben
In einer einfach verknüpften Liste zeigt der nächste Zeiger des letzten Knotens auf den ersten Knoten.
Doppelt verknüpfte Liste als Rundschreiben
In einer doppelt verknüpften Liste zeigt der nächste Zeiger des letzten Knotens auf den ersten Knoten und der vorherige Zeiger des ersten Knotens auf den letzten Knoten, wodurch das Kreis in beide Richtungen verläuft.
Gemäß der obigen Abbildung sind die folgenden wichtigen Punkte zu berücksichtigen.
Der nächste Link verweist auf den ersten Link der Liste, sowohl bei einfach als auch bei doppelt verknüpfter Liste.
Der vorherige Link des ersten Links zeigt bei doppelt verknüpfter Liste auf den letzten der Liste.
Grundoperationen
Im Folgenden sind die wichtigen Vorgänge aufgeführt, die von einer Rundschreibenliste unterstützt werden.
insert - Fügt ein Element am Anfang der Liste ein.
delete - Löscht ein Element vom Anfang der Liste.
display - Zeigt die Liste an.
Einfügevorgang
Der folgende Code demonstriert den Einfügevorgang in eine zirkuläre verknüpfte Liste basierend auf einer einzelnen verknüpften Liste.
Beispiel
insertFirst(data):
Begin
create a new node
node -> data := data
if the list is empty, then
head := node
next of node = head
else
temp := head
while next of temp is not head, do
temp := next of temp
done
next of node := head
next of temp := node
head := node
end if
End
Löschvorgang
Der folgende Code demonstriert den Löschvorgang in einer zirkulären verknüpften Liste basierend auf einer einzelnen verknüpften Liste.
deleteFirst():
Begin
if head is null, then
it is Underflow and return
else if next of head = head, then
head := null
deallocate head
else
ptr := head
while next of ptr is not head, do
ptr := next of ptr
next of ptr = next of head
deallocate head
head := next of ptr
end if
End
Listenbetrieb anzeigen
Der folgende Code demonstriert die Anzeigelistenoperation in einer zirkulären verknüpften Liste.
display():
Begin
if head is null, then
Nothing to print and return
else
ptr := head
while next of ptr is not head, do
display data of ptr
ptr := next of ptr
display data of ptr
end if
End
Um mehr über die Implementierung in der Programmiersprache C zu erfahren, klicken Sie bitte hier .