連結リスト（リンクリスト）の要素削除を徹底解説！C言語での実装例つき

連結リスト（リンクリスト）は動的メモリ割り当てを使用するデータ構造です。そのため、データの増減に応じてリストのサイズが自動的に伸縮します。

連結リストは「ノード」の集合として定義され、各ノードは次の2つの部分で構成されています。

• データ部：実際の値を格納する部分
• リンク部：次のノードへのポインタを格納する部分

データ・リンク・連結リスト全体のイメージは下図の通りです。

連結リストに対する主な操作

C言語における連結リストの基本操作には、次の3種類があります。

• 挿入
• 削除
• 走査（トラバーサル）

本記事では、この中でも特に重要な「削除」の処理について、具体例とともに詳しく解説します。

削除の仕組み

連結リストからノードを削除する場合、削除対象ノードの前のノードのリンクを、削除対象ノードの次のノードへ直接つなぎ替えます。こうすることで、リストのつながりを保ったまま対象ノードだけを取り外せます。

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

ノード2を削除する場合

ノード1を削除する場合

ノード3を削除する場合

サンプルプログラム（C言語）

続いて、連結リストから要素を削除するC言語のサンプルプログラムを紹介します。このプログラムでは、先頭への要素追加を行うpush関数、指定位置のノードを削除するdeleteNode関数、リスト内容を表示するprintList関数を実装しています。

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

// 先頭に新しいノードを挿入する関数
void push(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;

    // 先頭ノード（位置0）を削除する場合
    if (position == 0) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    // 削除対象ノードの直前のノードを探す
    for (int i = 0; temp != NULL && i < position - 1; i++)
        temp = temp->next;

    // 位置が範囲外の場合は何もしない
    if (temp == NULL || temp->next == NULL)
        return;

    // 対象ノードをスキップしてつなぎ替え
    struct Node *next = temp->next->next;
    free(temp->next); // メモリ解放
    temp->next = next;
}

// リストの内容を表示する関数
void printList(struct Node *node) {
    while (node != NULL) {
        printf(" %d ", node->data);
        node = node->next;
    }
}

int main() {
    struct Node* head = NULL;
    push(&head, 7);
    push(&head, 1);
    push(&head, 3);
    push(&head, 2);
    push(&head, 8);

    puts("Created List: ");
    printList(head);

    deleteNode(&head, 3);

    puts("\n List after Deletion at position 3: ");
    printList(head);

    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Created List:
8 2 3 1 7
List after Deletion at position 3:
8 2 3 7

まとめ

このように、連結リストの削除処理では前後のノードのリンクをつなぎ替えることがポイントです。配列とは異なり、要素を詰め直す必要がないため、削除処理を効率的に行えるのが連結リストの大きな利点といえます。ただし、free関数によるメモリ解放を忘れるとメモリリークの原因になるため、注意が必要です。