基本情報科目Bサンプル問題：問10　単方向リストの要素削除をマスターする：Pythonによる実装

単方向リストから要素を削除する手続きについて

単方向リスト（リンクリスト）は、コンピュータ科学の基本的なデータ構造の一つであり、「節（ノード）」という要素が次の節へのリンクを持つことで一連のデータを構成します。各ノードは通常、格納された「データ」と「次のノードへの参照（リンク）」を保持しています。

リストから要素を削除する7つのステップ

ステップ1：空のリストのチェック

リストが空でないことを確認します。もしリストが空なら、削除する対象が存在しないため処理を終了します。

ステップ2：削除する要素の特定

削除したい要素を「値」や「位置」によって特定します。

ステップ3：ノードの検索

リストの先頭（ヘッド）から順に巡回し、削除対象のノードを検索します。この際、削除するノードの「直前のノード」も特定しておく必要があります（リンクを繋ぎ変えるために不可欠です）。

ステップ4：ノードの削除（リンクの更新）

削除対象のノードが見つかったら、その直前のノードの参照先を、削除するノードの次のノードへと更新します。これにより、リストの連結から対象ノードが切り離されます。

ステップ5：メモリの解放

切り離されたノードを破棄してメモリを解放します。PythonやJavaのようなガベージコレクションがある言語では、参照がなくなった時点で自動的に処理されるため、明示的な記述は不要なことが多いです。

ステップ6：ヘッドノードの削除

削除対象がリストの先頭（ヘッド）である場合は、特別な処理が必要です。現在のヘッドの「次のノード」を、新たなヘッドとして設定します。

ステップ7：削除確認

最後に、正しく削除されたかを確認します。リストを再巡回し、対象の要素が存在しないことをチェックします。

Pythonによる実装例

1. ノードの定義

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

2. リストの定義と削除メソッド

class LinkedList:
    def __init__(self):
        self.head = None

    def delete_node(self, key):
        temp = self.head

        # 1. 削除するノードがヘッドノードの場合
        if (temp is not None):
            if (temp.data == key):
                self.head = temp.next
                temp = None
                return

        # 2. 削除するノードを探索（直前のノードを prev に保持）
        prev = None
        while(temp is not None):
            if temp.data == key:
                break
            prev = temp
            temp = temp.next

        # 3. ノードがリストに存在しなかった場合
        if(temp == None):
            return

        # 4. リンクを繋ぎ変えてノードを除外
        prev.next = temp.next
        temp = None

3. 実行例

llist = LinkedList()
llist.head = Node(1)
second = Node(2)
third = Node(3)
llist.head.next = second
second.next = third

print("Original Linked List:")
temp = llist.head
while(temp):
    print(temp.data, end=' ')
    temp = temp.next
print()

# 要素「2」を削除
llist.delete_node(2)

print("Linked List after deletion of 2:")
temp = llist.head
while(temp):
    print(temp.data, end=' ')
    temp = temp.next

まとめ

単方向リストの削除アルゴリズムを理解することは、メモリ上のデータの繋がりを意識する訓練になります。これは基本情報技術者試験の対策のみならず、効率的なプログラムを書くためのデータ構造の基礎体力を養うことに直結します。

問題演習で知識を定着させましょう。

サンプル問題問10

基本情報科目Bサンプル問題：問10 単方向リストの要素削除をマスターする：Pythonによる実装