双方向リンクリストの中央からノードを削除するPythonプログラム

双方向リンクリスト（Doubly Linked List）の中央からノードを削除するには、まず「Node」クラスを作成する必要があります。このクラスには3つの属性を定義します。ノードに格納されるデータ、リンクリスト上の次のノードへの参照（next）、そして前のノードへの参照（prev）です。

さらに、初期化関数を持つもう一つのクラスを作成します。このクラスのコンストラクタ内では、リストの先頭を示すheadが「None」に初期化されます。

加えて、リンクリストへノードを追加するメソッド、ノードを表示するメソッド、そして双方向リンクリストの中央からノードを削除するメソッドといった、複数のメソッドを定義していきます。

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

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

以下に、実際の動作を示すサンプルコードを紹介します。

サンプルコード

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

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

    def add_data(self, my_data):
        new_node = Node(my_data)
        if(self.head == 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 print_it(self):
        curr = self.head
        if (self.head == None):
            print("リストは空です")
            return
        print("双方向リンクリスト内のノード：")
        while curr != None:
            print(curr.data)
            curr = curr.next

    def delete_from_middle(self):
        if(self.head == None):
            return
        else:
            curr = self.head
            mid = (self.size // 2) if (self.size % 2 == 0) else ((self.size + 1) // 2)
            for i in range(1, mid):
                curr = curr.next
            if(curr == self.head):
                self.head = curr.next
                self.tail.next = None
            elif(curr == self.tail):
                self.tail = self.tail.prev
            else:
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
            current = None
        self.size = self.size - 1

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(92)
my_instance.print_it()
while(my_instance.head != None):
    my_instance.delete_from_middle()
    print("中央から要素を削除した後のリスト：")
    my_instance.print_it()

実行結果

要素を双方向リンクリストに追加しています
双方向リンクリスト内のノード：
10
24
54
77
92
中央から要素を削除した後のリスト：
双方向リンクリスト内のノード：
24
54
77
92
中央から要素を削除した後のリスト：
双方向リンクリスト内のノード：
54
77
92
中央から要素を削除した後のリスト：
双方向リンクリスト内のノード：
77
92
中央から要素を削除した後のリスト：
双方向リンクリスト内のノード：
92
中央から要素を削除した後のリスト：
リストは空です

コードの解説

• まず「Node」クラスを作成します。
• 必要な属性を持つ別のクラス（double_list）を作成します。
• 「add_data」メソッドを定義し、双方向リンクリストの末尾にデータを追加できるようにします。
• 「print_it」メソッドを定義し、リンクリスト内のすべてのノードを表示できるようにします。
• 「delete_from_middle」メソッドを定義し、リストの中央にあるノードを削除して、前後のノード同士を直接つなぎ替えます。
• 「__init__」メソッドでは、headとtailをNoneに、リストのサイズを0に初期化します。
• 「double_list」クラスのオブジェクトを作成し、データを追加した後にメソッドを呼び出して、中央から順番にノードを削除します。
• リストが空になるまで繰り返し処理を行い、毎回中央のノードを削除します。
• 「print_it」メソッドを使って、削除後のリストの状態をコンソールに表示します。

ポイント解説

中央位置の計算では、リストのサイズが偶数の場合は「size // 2」、奇数の場合は「(size + 1) // 2」を使って中央のインデックスを求めています。また、削除対象のノードがheadやtailであるケースも考慮されており、それぞれ適切にポインタが更新されます。それ以外の一般のノードの場合は、「curr.prev.next = curr.next」と「curr.next.prev = curr.prev」の2行によって、削除対象ノードをリンクから外しています。

なお、この削除操作の時間計算量はO(n)です。中央の位置までノードをたどる必要があるためです。一方、双方向リンクリストは前後双方へのポインタを持つため、削除時のリンクの付け替え自体はO(1)で行える点が大きな利点といえます。