Pythonで単方向リンクリストを循環リンクリストに変換する方法

単方向リンクリスト(片方向連結リスト)を循環リンクリストへ変換する必要がある場合、convert_to_circular_list というメソッドを定義します。このメソッドは、リストの最後のノードが先頭のノードを指すようにすることで、リスト全体を循環構造にします。

以下に具体的な実装例を示します。

サンプルコード

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList_struct:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_elements(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

def convert_to_circular_list(my_list):
    if my_list.last_node:
        my_list.last_node.next = my_list.head

def last_node_points(my_list):
    last = my_list.last_node
    if last is None:
        print('The list is empty...')
        return
    if last.next is None:
        print('The last node points to None...')
    else:
        print('The last node points to element that has {}...'.format(last.next.data))

my_instance = LinkedList_struct()

my_input = input('Enter the elements of the linked list.. ').split()
for data in my_input:
    my_instance.add_elements(int(data))

last_node_points(my_instance)

print('The linked list is being converted to a circular linked list...')
convert_to_circular_list(my_instance)

last_node_points(my_instance)

実行結果

Enter the elements of the linked list.. 56 32 11 45 90 87
The last node points to None...
The linked list is being converted to a circular linked list...
The last node points to element that has 56...

コードの解説

• まず、ノードのデータと次ノードへの参照を持つ Node クラスを作成します。

• 次に、必要な属性を備えた LinkedList_struct クラスを定義します。

• このクラスには __init__(イニシャライザ)があり、先頭ノード(head)と最終ノード(last_node)を初期値 None として初期化します。

• add_elements メソッドは、リンクリストの末尾に新しい要素を追加するために使用されます。リストが空の場合は新規ノードが head となり、そうでなければ既存の最終ノードの next に新しいノードを接続します。

• convert_to_circular_list メソッドは、最終ノードの next 参照を先頭ノード(head)に向けることで、リストを循環構造に変換します。

• last_node_points メソッドは、リストが空であるか、最終ノードが None を指しているか、あるいは特定のノードを指しているかを確認し、その状態を出力します。

• LinkedList_struct クラスのインスタンス(オブジェクト)を生成します。

• ユーザーからリンクリストに格納する要素を入力として受け取ります。

• 入力された各要素を順番にリンクリストへ追加していきます。

• 変換前に last_node_points メソッドを呼び出し、現状の最終ノードの参照先を確認します。

• convert_to_circular_list を実行してリストを循環化した後、再度参照先を確認すると、最終ノードが先頭の要素(56)を指していることがコンソールに出力され、循環リンクリストへの変換が成功したことがわかります。