Pythonで連結リストの指定位置の直前に新しい要素を挿入する方法

はじめに

連結リスト（Linked List）に複数の要素が格納されており、指定した位置 pos の直前に新しい値 val を挿入したいケースは、データ構造の学習において非常に重要なトピックです。本記事では、Python を使って単方向連結リストの指定インデックスの直前に要素を挿入するプログラムを分かりやすく解説します。

例えば、nums = [1,5,3,6,8]、pos = 3、val = 7 という入力が与えられた場合、出力は [1,5,3,7,6,8] となります。つまり、インデックス3の位置にある「6」の直前に新しい値「7」が挿入されることになります。

アルゴリズムの手順

この問題は、以下の手順に従って解くことができます。

• 挿入する値 val と同じ値を持つ新しいノード new を作成します。
• pos が 0 の場合（先頭への挿入）：
  • new の next に list_head を設定します。
  • new を返します。
• temp に list_head を代入します。
• temp が NULL ではなく、かつ pos が 1 でない間、以下を繰り返します。
  • temp を次のノードへ進めます。
  • pos を 1 減らします。
• new の next に temp の next を設定します。
• temp の next に new を設定し、リンクを繋ぎ替えます。
• list_head を返します。

実装例

理解を深めるために、以下の実装例を見てみましょう。

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

    def make_list(elements):
        head = ListNode(elements[0])
        for element in elements[1:]:
            ptr = head
            while ptr.next:
                ptr = ptr.next
            ptr.next = ListNode(element)
        return head

    def print_list(head):
        ptr = head
        print('[', end="")
        while ptr:
            print(ptr.val, end=", ")
            ptr = ptr.next
        print(']')

    def solve(list_head, pos, val):
        new = ListNode(val)
        if pos == 0:
            new.next = list_head
            return new

        temp = list_head
        while temp and pos != 1:
            temp = temp.next
            pos -= 1
        next = temp.next
        temp.next = new

    return list_head

nums = [1,5,3,6,8]
pos = 3
val = 7

list_head = make_list(nums)
list_head = solve(list_head, pos, val)
print_list(list_head)

入力例

[1,5,3,6,8], 3, 7

出力例

[1, 5, 3, 7, 6, 8]

処理のポイントと計算量

このアルゴリズムでは、まず pos が 0 かどうかを判定し、先頭への挿入の場合は特別な処理を行います。それ以外の場合は、temp ノードを挿入位置の直前まで移動させた後、ポインタを繋ぎ替えることで新しいノードを挿入します。

• 時間計算量： 挿入位置までリンクを辿るため、最悪で O(n) となります（n はリストの長さ）。
• 空間計算量： 新しいノード1個分のみ追加されるため、O(1) です。

配列とは異なり、連結リストでは既存の要素をずらすことなく、ポインタの付け替えだけで挿入が完了できる点が大きな特徴です。