Pythonで双方向リンクリストの要素を検索する方法【サンプルコード付きで解説】

双方向リンクリスト（Doubly Linked List）内の特定の要素を検索するには、まず「Node」クラスを作成する必要があります。このクラスには3つの属性を持たせます。ノードに格納されるデータ、リンクリストにおける次のノードへの参照、そして前のノードへの参照です。

さらに、初期化用のコンストラクタを持つ別のクラスを作成し、その中で先頭ノード（head）を「None」で初期化します。

その後、ユーザーが定義する複数のメソッドとして、リンクリストへノードを追加するメソッド、ノードを表示するメソッド、そして特定のノードを検索するメソッドを実装していきます。

双方向リンクリストの仕組み

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

サンプルコード

以下に、双方向リンクリスト内の要素を検索するプログラムの実装例を示します。

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

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

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

    def print_it(self):
        curr = self.head
        if (self.head == None):
            print("リストは空です")
            return
        print("双方向リンクリスト内のノード：")
        while curr != None:
            print(curr.data)
            curr = curr.next

    def search_node(self, val_to_search):
        i = 1
        flag_val = False
        curr = self.head
        if(self.head == None):
            print("リストは空です")
            return
        while(curr != None):
            if(curr.data == val_to_search):
                flag_val = True
                break
            curr = curr.next
            i = i + 1
        if(flag_val):
            print("ノードはリスト内の次の位置に存在します：")
            print(i)
        else:
            print("ノードはリスト内に存在しません")

my_instance = double_list()
print("双方向リンクリストに要素を追加しています")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
my_instance.add_data(77)
my_instance.add_data(24)
my_instance.add_data(0)
my_instance.print_it()
print("要素77を検索しています...")
my_instance.search_node(77)
print("要素7を検索しています...")
my_instance.search_node(7)

実行結果

双方向リンクリストに要素を追加しています
双方向リンクリスト内のノード：
10
24
54
77
24
0
要素77を検索しています...
ノードはリスト内の次の位置に存在します：
4
要素7を検索しています...
ノードはリスト内に存在しません

コードの解説

• まず「Node」クラスを作成し、前ノード・データ・次ノードの3つの属性を定義します。
• 続いて、必要な属性を持つ「double_list」クラスを作成します。
• 「add_data」メソッドを定義し、リンクリストの末尾に新しいデータを追加できるようにします。
• 「search_node」メソッドを定義し、引数として検索対象の値を受け取ります。
• このメソッドはリスト内を順番に走査して要素を探し、見つかった場合はその位置（インデックス）を返します。
• 「print_it」メソッドを定義し、リンクリストの内容をコンソールに表示します。
• 「double_list」クラスのインスタンスを生成し、add_dataメソッドを使ってデータを追加します。
• 「search_node」メソッドを呼び出すと、リンクリスト内のノードを反復処理し、目的の要素が見つかればその位置を出力します。

計算量について

この検索処理は線形探索のため、最悪の場合リスト全体を走査することになり、時間計算量はO(n)となります。また、双方向リンクリストは各ノードが前後両方のポインタを持つため、片方向リンクリストと比べてメモリ消費量はやや多くなりますが、逆方向からの走査や削除処理が効率的に行えるというメリットがあります。