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

双方向リンクリスト(ダブルリンクリスト)のノード数をカウントするには、まず「Node」クラスを作成する必要があります。このクラスには3つの属性を定義します。ノードが保持するデータ(data)、次のノードへの参照(next)、そして前のノードへの参照(prev)です。

双方向リンクリストでは、各ノードがポインタを持ちます。現在のノードは、次のノードと前のノードの両方へのポインタを保持しています。リストの末尾にあるノードは、nextポインタに「NULL」(PythonではNone)を格納します。この構造により、リストは前方・後方のどちらの方向にも走査できるのが特徴です。

以下に、具体的なコード例を示します。

サンプルコード

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def add_data(self, my_data):
        new_node = Node(my_data)
        if self.head is None:
            self.head = self.tail = new_node
            self.head.prev = None
            self.tail.next = None
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
            self.tail.next = None

    def count_node(self):
        my_counter = 0
        curr = self.head
        while curr is not None:
            my_counter += 1
            curr = curr.next
        return my_counter

    def print_it(self):
        curr = self.head
        if self.head is None:
            print("リストは空です")
            return
        print("ノードの内容:")
        while curr is not None:
            print(curr.data)
            curr = curr.next

my_instance = DoublyLinkedList()
print("リストに要素を追加しています")
my_instance.add_data(10)
my_instance.add_data(14)
my_instance.add_data(24)
my_instance.add_data(17)
my_instance.add_data(22)
my_instance.print_it()
print("双方向リンクリスト内のノード数:")
print(my_instance.count_node())

実行結果

リストに要素を追加しています
ノードの内容:
10
14
24
17
22
双方向リンクリスト内のノード数:
5

コードの解説

• 「Node」クラスを作成します。このクラスには、ノードが保持するデータ(data)、前のノードへの参照(prev)、次のノードへの参照(next)という3つの属性を定義しています。
• リンクリスト本体を管理する「DoublyLinkedList」クラスを作成し、リストの先頭(head)と末尾(tail)への参照を属性として持ちます。
• __init__メソッドでは、headとtailをNoneに初期化し、空のリスト状態からスタートできるようにします。
• 「add_data」メソッドを定義します。新しいノードを生成し、リストが空の場合はheadとtailに設定し、そうでなければ末尾に連結してtailを更新することで、データをリストの末尾へ追加します。
• 「count_node」メソッドを定義します。headから順にnextポインタをたどりながらカウンターを1ずつ増やし、最終的なノード数を返します。
• 「print_it」メソッドを定義します。リストが空の場合はその旨を表示し、そうでなければ全ノードのデータを順番に出力します。
• クラスのインスタンスを生成し、「add_data」メソッドを使って10、14、24、17、22の5つの要素をリストに追加します。
• 「count_node」メソッドを呼び出してノード数を取得し、print関数でコンソールに表示します。

なお、count_nodeメソッドはリスト内の全ノードを一度ずつ訪問するため、計算量はO(n)となります。ノード数が多い場合でも線形時間でカウントでき、双方向リンクリストの基本的な操作を理解するうえで非常に有用な実装例です。