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 .