環状リストとは？
環状リスト、または循環リストとは、データ構造の一つで、リストの末尾が先頭に接続された構造を持っているものを指します。つまり、最後の要素が最初の要素に繋がっており、要素が循環的に繋がっているため、ループが簡単に実現されます。
このデータ構造は、一方向リストや双方向リストと同様に、格納されている要素の順序が重要である場合に使用されます。環状リストには、多くの利点があります。たとえば、非常に効率的なデータ挿入や削除、そして簡単な循環処理が可能である点が挙げられます。
環状リストの実装方法
環状リストは、一方向リストや双方向リストと同様に、ノード（要素）の連結で表現されます。ノードは、データを格納する要素と、次または前の要素への参照（ポインタ）を持っています。
環状リストは、循環処理が前提であるため、一方向リストや双方向リストと異なる点があります。通常、最初のノードはheadと呼ばれ、最後のノードはtailと呼ばれます。各ノードには、次のノードへの参照が格納され、最後のノードの参照はheadに接続されます。これらの参照がループを形成し、リストが環状リストとして動作するようになります。
環状リストの実装例
以下は、環状リストをPythonで実装する例です。
“`python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
self.tail = new_node
new_node.next = self.head
else:
self.tail.next = new_node
self.tail = new_node
self.tail.next = self.head
def display(self):
current = self.head
if self.head is None:
print(“List is empty”)
else:
while current.next is not self.head:
print(current.data)
current = current.next
print(current.data)
c_list = CircularLinkedList()
c_list.append(1)
c_list.append(2)
c_list.append(3)
c_list.append(4)
c_list.display()
“`
この例では、`Node`クラスでノードを表現し、`CircularLinkedList`クラスで環状リストを表現しています。`append`メソッドでは、新しい要素をリストの末尾に追加します。`display`メソッドでは、リスト全体を表示します。
環状リストは、効率的なデータ構造として様々な用途に利用されます。上記の実装例を基に、環状リストを活用したアルゴリズムやデータ処理の実装など、さまざまな応用が可能です。
参考記事
合わせて読みたい
【Google Chrome】右クリックで翻訳がでなくなった時の対策方法の決定版