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

双方向リンクリスト（Doubly Linked List）の先頭に新しいノードを挿入するには、まず「Node」クラスを作成する必要があります。このクラスには、ノードが保持するデータ、リンクリスト上の次のノードへの参照、前のノードへの参照という3つの属性を定義します。

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

サンプルコード

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      # 末尾ノード

    # 先頭にデータを追加するメソッド
    def add_data_at_start(self, my_data):
        new_node = Node(my_data)
        if self.head is None:
            # リストが空の場合
            self.head = self.tail = new_node
        else:
            # 既存の先頭ノードの前に新しいノードをつなぐ
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    # リストの内容を表示するメソッド
    def print_it(self):
        curr = self.head
        if self.head is None:
            print("The list is empty")
            return
        print("The nodes in the doubly linked list are :")
        while curr is not None:
            print(curr.data)
            curr = curr.next


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

実行結果

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

コードの解説

• まず「Node」クラスを作成します。各ノードは、保持するデータ（data）、前のノードへの参照（prev）、次のノードへの参照（next）の3つの属性を持ちます。
• 続いて、リンクリスト本体を管理するための「double_list」クラスを作成します。
• 「add_data_at_start」メソッドを定義し、双方向リンクリストの先頭にデータを追加できるようにします。
• 「print_it」メソッドを定義し、リンクリスト内のノードを先頭から順番に表示します。
• 「__init__」メソッドでは、head（先頭）とtail（末尾）のポインタをNoneで初期化します。
• 「double_list」クラスのインスタンスを生成し、メソッドを呼び出してリストの先頭へデータを追加していきます。
• 要素を追加するたびに、新しいノードがリストの先頭に挿入され、既存のノードは後ろにずれていきます。
• 挿入後のリストの状態は、「print_it」メソッドを使ってコンソールに表示されます。

計算量について

双方向リンクリストの先頭への挿入は、headポインタを付け替えるだけで完了するため、要素数に関係なくO(1)の計算量で実行できます。これは配列の先頭への挿入（全要素をずらす必要がありO(n)）と比較して大きな利点です。