データ構造-循環リンクリスト

循環リンクリストは、最初の要素が最後の要素を指し、最後の要素が最初の要素を指すリンクリストのバリエーションです。単一リンクリストと二重リンクリストの両方を循環リンクリストにすることができます。

循環としての単一リンクリスト

単一リンクリストでは、最後のノードの次のポインタが最初のノードを指します。

循環としての二重リンクリスト

二重リンクリストでは、最後のノードの次のポインタが最初のノードを指し、最初のノードの前のポインタが最後のノードを指し、両方向に循環します。

上図のように、考慮すべき重要な点は次のとおりです。

最後のリンクの次は、単一リンクリストと二重リンクリストの両方の場合に、リストの最初のリンクを指します。
二重リンクリストの場合、最初のリンクの前はリストの最後を指します。

基本操作

以下は、循環リストでサポートされている重要な操作です。

insert −リストの先頭に要素を挿入します。
delete −リストの先頭から要素を削除します。
display −リストを表示します。

挿入操作

次のコードは、単一のリンクリストに基づく循環リンクリストへの挿入操作を示しています。

例

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

削除操作

次のコードは、単一のリンクリストに基づく循環リンクリストでの削除操作を示しています。

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

ディスプレイリストの操作

次のコードは、循環リンクリストでのリストの表示操作を示しています。

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

Cプログラミング言語での実装については、ここをクリックしてください。