C++で指定した位置の連結リストノードを削除する方法

はじめに

このチュートリアルでは、単方向連結リスト（Singly Linked List）から、指定された位置にあるノードを削除する方法を解説します。まずは、問題を解決するための手順を確認していきましょう。

解決の手順

• データ（data）と次ノードへのポインタ（next）を持つ構造体を定義します。

• ノードを単方向連結リストの先頭に挿入する関数を作成します。

• ダミーデータを使って単方向連結リストを初期化します。

• 削除対象ノードの位置を指定します。

• 連結リストを走査し、指定された位置にあるノードを特定します。

• ノードを削除する関数を作成します。削除処理では、以下の3つのケースを考慮する必要があります。

  • 先頭ノードの場合：headポインタを次のノードへ移動します。

  • 中間ノードの場合：前のノードのリンクを、その次のノードにつなぎ替えます。

  • 末尾ノードの場合：前のノードからのリンクを解除します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

// データと次ノードへのポインタを持つ構造体
struct Node {
    int data;
    struct Node *next;
};

// リストの先頭に新しいノードを挿入する関数
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// 指定された位置のノードを削除する関数
void deleteNode(struct Node **head_ref, int position) {
    // リストが空の場合は何もしない
    if (*head_ref == NULL) {
        return;
    }
    struct Node* temp = *head_ref;
    // ケース1：先頭ノードを削除する場合
    if (position == 1) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    // 削除対象ノードの直前まで移動する
    for (int i = 2; temp != NULL && i < position; i++) {
        temp = temp->next;
    }
    // 指定位置がリストの長さを超える場合は何もしない
    if (temp == NULL || temp->next == NULL) {
        return;
    }
    // ケース2・3：中間または末尾ノードを削除する場合
    struct Node *next = temp->next->next;
    free(temp->next);
    temp->next = next;
}

// 連結リストの内容を表示する関数
void printLinkedList(struct Node *node) {
    while (node != NULL) {
        cout << node->data << "->";
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    insertNode(&head, 1);
    insertNode(&head, 2);
    insertNode(&head, 3);
    insertNode(&head, 4);
    insertNode(&head, 5);
    cout << "Linked list before deletion:" << endl;
    printLinkedList(head);
    deleteNode(&head, 1);
    cout << "\nLinked list after deletion:" << endl;
    printLinkedList(head);
    return 0;
}

実行結果

上記のプログラムを実行すると、以下のような出力が得られます。

Linked list before deletion:
5->4->3->2->1->
Linked list after deletion:
4->3->2->1->

まとめ

このチュートリアルでは、単方向連結リストから指定した位置のノードを削除する方法を学びました。重要なのは、削除対象が先頭・中間・末尾のどれに該当するかを判定し、それぞれに応じてポインタを適切につなぎ替えることです。特に先頭ノードを削除する場合は、headポインタ自体を更新する必要がある点に注意しましょう。

本チュートリアルについてご不明な点や質問がある場合は、ぜひコメント欄でお知らせください。