【Python】双方向リンクリストの中央に新しいノードを挿入するプログラム

双方向リンクリスト（Doubly Linked List）の中央に新しいノードを挿入したい場合、まず「Node」クラスを作成する必要があります。このクラスには、ノードに格納するデータ、次のノードへの参照（next）、前のノードへの参照（previous）という3つの属性を持たせます。

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

コード例

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
        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.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
        self.size = self.size + 1

    def print_it(self):
        curr = self.head
        if (self.head == None):
            print("The list is empty")
            return
        print("The nodes in the doubly linked list are :")
        while curr != None:
            print(curr.data)
            curr = curr.next

    def add_data_in_middle(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:
            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
            temp = curr.next
            temp.previous = curr
            curr.next = new_node
            new_node.previous = curr
            new_node.next = temp
            temp.previous = new_node
        self.size = self.size + 1

my_instance = double_list()
print("Elements are being added to the doubly linked list")
my_instance.add_data(10)
my_instance.add_data(24)
my_instance.add_data(54)
print("Elements are added to the middle of the list")
my_instance.add_data_in_middle(77)
my_instance.print_it()
my_instance.add_data_in_middle(92)
my_instance.print_it()

出力結果

Elements are being added to the doubly linked list
Elements are added to the middle of the list
The nodes in the doubly linked list are :
10
24
77
54
The nodes in the doubly linked list are :
10
24
92
77
54

解説

• ノードの構造を定義する「Node」クラスを作成します。
• リンクリスト本体を管理するための属性を持つ「double_list」クラスを作成します。
• 双方向リンクリストの中央インデックスにデータを追加するメソッド「add_data_in_middle」を定義します。
• リストの末尾にノードを追加するメソッド「add_data」を定義します。
• リンクリスト内のすべてのノードを表示するメソッド「print_it」を定義します。
• 「double_list」クラスのインスタンスを生成し、各メソッドを呼び出してデータを追加していきます。
• 「add_data_in_middle」を呼び出すことで、リンクリストの中央にデータを挿入できます。
• 初期化用の「__init__」メソッドでは、head（先頭）とtail（末尾）をNoneに設定し、要素数を管理するsizeを0で初期化します。
• 最後に「print_it」メソッドを使って、結果をコンソールに表示します。

中央位置の計算ロジック

挿入位置となる中央インデックスは、要素数が偶数の場合は size // 2、奇数の場合は (size + 1) // 2 で求められます。これにより、リストの要素数に関わらず、常に中央付近に新しいノードが挿入される仕組みになっています。

ノード挿入時のポイント

中央にノードを挿入する際は、参照（ポインタ）の付け替え順序が非常に重要です。既存ノード同士の接続を変更する前に、挿入位置の後続ノードへの参照を一時変数 temp に保存しておくことで、リンク切れを防ぐことができます。その後、新ノードと前後ノードの previous・next を適切に再設定することで、リストの中央へ安全にノードを組み込めます。