PythonでN個のノードを持つ循環リンクリストを作成し、ノード数をカウントする方法

この記事では、Pythonを使って「N」個のノードを持つ循環リンクリスト（Circular Linked List）を作成し、そのノード数をカウントする方法を解説します。

まず、リストの各要素を表す「Node」クラスを定義します。このクラスには、ノードが保持するデータと、次のノードへの参照という2つの属性があります。循環リンクリストでは、先頭（head）と末尾（rear）が互いに隣接しており、全体が円形につながっています。そのため、最後のノードのnextには「NULL」ではなく、先頭ノードへの参照が格納される点が通常のリンクリストとの大きな違いです。

続いて、データを追加するための関数「add_data」と、ノード数をカウントするための関数「count_node」を定義します。以下に実際のコード例を示します。

サンプルコード

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

def add_data(head_ref, my_data):
    ptr_1 = Node(0)
    temp = head_ref
    ptr_1.data = my_data
    ptr_1.next = head_ref

    if (head_ref != None):
        while (temp.next != head_ref):
            temp = temp.next
        temp.next = ptr_1
    else:
        ptr_1.next = ptr_1

    head_ref = ptr_1
    return head_ref

def count_node(head):
    temp = head
    result = 0
    if (head != None):
        while True:
            temp = temp.next
            result = result + 1
            if (temp == head):
                break
    return result

if __name__=='__main__':
    head = None
    head = add_data(head, 78)
    head = add_data(head, 56)
    head = add_data(head, 22)
    print("Elements are added to list")
    print("The number of nodes are : ")
    print(count_node(head))

実行結果

Elements are added to list
The number of nodes are :
3

コードの解説

• まず「Node」クラスを定義します。コンストラクタでデータと次ノードへの参照を初期化します。
• 「add_data」関数は、新しいノードを循環リンクリストに追加します。リストが空の場合は、自分自身を指す単一ノードとして初期化されます。既存のノードがある場合は、最後のノードまでたどり、そこに新しいノードを接続して循環構造を維持します。
• 「count_node」関数は、先頭ノードから出発して一周するまでノードを順にたどり、通過したノードの数をカウントします。tempが再びheadに戻った時点でループを終了することで、無限ループを防いでいます。
• メイン処理では、空のリストに対して78、56、22という3つの値を順番に追加しています。
• 最後に「count_node」関数を呼び出し、ノード数である「3」が出力されます。

このように、循環リンクリストは終端がNULLを持たない代わりに先頭へ戻る構造のため、ノード数のカウントや走査を行う際には「先頭に戻ってきたかどうか」を判定条件にすることが重要なポイントです。