Circular Linked Listsは、リストを格納するためのデータ構造です。
これはリンクリストに非常に似ていますが、いくつかの追加機能があります。
この記事では、循環リンクリストとは何かを説明し、pythonで実装し、その出力を見ます。
この記事もチェック：Pythonで連結リスト(リンクリスト)をクラスで実装する方法
Pre-Requisite: リンクリストの理解
循環リンクリストの説明に移る前に、まずリンクリストを定義する必要があります。
リンクリストとは、リスト項目が他のリスト項目と特定の方法でリンクされているリストのことです。
リンクリストの形式によって、オブジェクトをリンクする方法は異なります。
単一リンクリスト」または単に「リンクリスト」は最も一般的なリンクリストで、各項目がリスト内の次の項目にリンクしています。
つまり、10番目の項目にアクセスするためには、まず10番目の項目にリンクしている9番目の項目にアクセスする必要がある。
そして、10番目の項目にアクセスしたら、10番目の項目の接続を通じて、11番目の項目にアクセスできるようになる。
ノードとは、リンクリストの各オブジェクトにつけられた名前です。
単一リンクリストの各ノードは、2つの構成要素を持っている。
最初の部分にはノードのデータが含まれ、2番目の部分には次のノードへのリンクが含まれる。
では、次に循環型リンクリストについて見てみましょう。
この記事もチェック：Pythonのリストの最初と最後の要素を取得する方法を解説する
Pythonで作る円形リンクリスト
循環リンクリストは、ノードがリンクでつながっている点ではリンクリストと似ていますが、最後のノードも何もリンクしていないのではなく、最初のノードにリンクしています。
つまり、最後のノードにアクセスした後、最後のノードを経由して最初のノードにアクセスすることができるのです。
この方法は、最後のノードのリンクを None として保持するのではなく、代わりに最初のノードを指すようにするだけです。
この方法の利点は、循環的にやってくるアイテムのリストを持つアルゴリズムを簡単に実装できるようになることです。
例えば、ラウンドロビンスケジューリングアルゴリズムや、マルチプレイヤーゲームにおけるプレイヤーのターンは、本質的に循環的なものです。
視覚化すると、循環型リンクリストは以下のような形になります。
class Node:
def __init__(self, data = None):
self.data = data
self.next = self
|
上の例では、リスト内に4つのノードがあることがわかる。
各ノードは何らかのデータを持っており、リストの最初のノードにリンクしている最後のノードを除いて、各ノードはリストの次のノードにリンクしています。
リストの先頭を指すheadは、リストに入り、循環リンクリストを反復するために使用されます。
おすすめ記事 – 双方向リンクリスト
この記事もチェック：Pythonの双方向連結リストの実装方法を解説する
Python で環状リンクリストを実装する
循環リンクリストを作成するために、2つのクラスを作成します。
1つ目はノード用のクラス、2つ目はノードを使用するリンクリスト用のクラスです。
クラス ノード
ノード・クラスでは、2つのメンバを持ちます。
ひとつはデータを格納するためのもので、もうひとつは次のノードへのリンクを格納するためのものです。
クラス定義は次のようになる。
class CLL:
def __init__(self):
self.head = None
self.count = 0
def __repr__(self):
string = ""
if(self.head == None):
string += "Circular Linked List Empty"
return string
string += f"Circular Linked List: temp = self.head.next
while(temp != self.head):
string += f" -> {temp.data}"
temp = temp.next
return string
def append(self, data):
self.insert(data, self.count)
return
def insert(self, data, index):
if (index > self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if self.head == None:
self.head = Node(data)
self.count += 1
return
temp = self.head
for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
temp = temp.next
aftertemp = temp.next #New node goes between temp and aftertemp
temp.next = Node(data)
temp.next.next = aftertemp
if(index == 0):
self.head = temp.next
self.count += 1
return
def remove(self, index):
if (index >= self.count) | (index < 0):
raise ValueError(f"Index out of range: {index}, size: {self.count}")
if self.count == 1:
self.head = None
self.count = 0
return
before = self.head
for _ in range(self.count - 1 if index - 1 == -1 else index - 1):
before = before.next
after = before.next.next
before.next = after
if(index == 0):
self.head = after
self.count -= 1
return
def index(self, data):
temp = self.head
for i in range(self.count):
if(temp.data == data):
return i
temp = temp.next
return None
def size(self):
return self.count
def display(self):
print(self)
|
つまり、最初に作られた新しいノードは、それがどのように作られたかによってデータの値を持ったり持たなかったりするが、デフォルトで自分自身を指すので、1項目の循環リンクリストのようになる。
クラス 円形リンクリスト
このクラスは、前のクラスで作成されたノードを使用して、円形リンクリストを実装します。
このクラスは、1つのヘッド・ノード、1つのカウント・メンバ、および特定のタスクのための複数のメソッドを含んでいます。
上に書いたメソッドについて説明します。
__init__ メソッド
リストにはノードが存在しないので head を None に設定し、同じ理由で count を 0 に設定しています。
repr` メソッド
リンクリストを表示する文字列は __repr__ の処理で返されます。
つまり、リストが空の場合はそれを表示し、リストが空でない場合は各ノードのデータを 1 つずつ表示します。
appendとinsert` メソッド
この実装では、指定した位置にノードを追加したり挿入したりすることができます。
追加する場合は、単純に insert メソッドを呼び出して、リストのサイズを index として送信します。
Insertメソッドでは、まず指定したインデックスが有効かどうかをチェックし、有効でない場合はValueErrorを投げる。
チェックに合格した後、リストが空の場合は、単に新しいノードをheadに代入し、count` をインクリメントして、メソッドからリターンします。
リストが空でない場合は、まず指定されたインデックスの前にあるノードに到達します。
例えば、指定されたインデックスが 5 であれば、4 番目のインデックスにあるノードに到達します。
リストは循環しているので、指定されたインデックスが 0 であれば、リストの最後のノードに到達することになります。
ここで、新しいノードを指定されたインデックスの前のノードの next に割り当て、新しいノードの next を指定されたインデックスのノードにリンクするようにします。
これにより、新しいノードが指定されたインデックスの前に挿入され、そのインデックスを取得して前に押し出されることが確認されます。
ここで、指定されたインデックスが 0 の場合、リストの最後のノードの後にノードを挿入しているので、単に head が新しいノードを指すようにし、それをリストの新しいヘッドとします。
remove` メソッド
項目を削除するには、その項目を削除する場所を指定する必要があります。
指定したインデックスが範囲外の場合は、 ValueError を発生させます。
リストに 1 つしかない場合は、単純に head を None に、 count を 0 にして、メソッドから戻ります。
それ以外の場合は、指定したインデックスの前のノードと、指定したインデックスの後のノードに到達する必要がある。
例えば、指定されたインデックスが 4 であれば、3番目のノードと5番目のノードに到達する必要があり、指定されたインデックスが 0 であれば、リストは循環するので、最後のノード（その前）と最初のノード（その後）に到達する必要があります。
この後、指定されたインデックスの後のノードを、指定されたインデックスの前のノードの next に代入するだけです。
これにより、指定されたインデックスのノードはスキップされ、リストから削除されます。
もし、指定したインデックスが0であれば、headはリストから削除されているので、指定したインデックスの後にあるノードをheadに代入すれば、リストが復元されます。
このとき、リストの count をデクリメントすることを忘れないでください。
インデックス、サイズ、表示メソッド
indexメソッドはリスト内の項目を検索します。
見つかった場合はそのインデックスを返し、そうでない場合はNoneを返します。
size メソッドはリストに含まれるノードの数を返し、 display メソッドはリストを表示します。
The Output
Fake tag
Fake tag
おわりに
Pythonで円形リンクリストとその使い方について学びました。
まず、単一リンクリストがどのように機能するかを見て、次に円形リンクリストがどのように異なるかを見ていきました。
Pythonでデータ構造のコードを書き、それぞれのメソッドがどのように動作するかを議論し、そしてコードの結果を見ました。
次回のチュートリアルでお会いしましょう。