Pythonで連結リストのノードを削除する方法

連結リスト（リンクリスト）にいくつかの要素が格納されているとします。ここでの課題は、指定されたノードをリストから削除する関数を作成することです。例えば、リストが 1 → 3 → 5 → 7 → 9 の場合、値 3 を削除すると、結果は 1 → 5 → 7 → 9 になります。

削除の基本的な考え方

削除したいノードを指すポインタ「node」が与えられている場合、以下の2つの操作を実行することでノードを削除できます。

• node.val = node.next.val — 次のノードの値を現在のノードにコピーする
• node.next = node.next.next — 現在のノードの参照先を、次の次のノードに付け替える

この手法は、削除対象ノードの前のノードが分からない場合でも機能するのが特徴です。値を一つずつ前へずらすことで、実質的にそのノードを消し去ることができます。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

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(']')

class Solution(object):
    def deleteNode(self, node, data):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        while node.val is not data:
            node = node.next
        node.val = node.next.val
        node.next = node.next.next

head = make_list([1,3,5,7,9])
ob1 = Solution()
ob1.deleteNode(head, 3)
print_list(head)

入力

linked_list = [1,3,5,7,9]
data = 3

出力

[1, 5, 7, 9]

コードの解説

このプログラムでは、まず make_list 関数を使って配列 [1, 3, 5, 7, 9] から連結リストを構築しています。続いて Solution クラスの deleteNode メソッドが呼び出され、削除したい値 3 を持つノードまでポインタを進めた後、上述の2つの操作によってノードを削除します。

最後に print_list 関数でリスト全体を出力しており、値 3 が取り除かれた [1, 5, 7, 9] が表示されることが確認できます。

なお、この手法には注意点もあります。削除対象がリストの末尾のノードである場合、node.next が存在しないためエラーになります。また、時間計算量は O(1) で非常に効率的ですが、末尾ノードの削除が必要なケースでは、従来通り前のノードを辿る方式（O(n)）を採用する必要があります。