C++でリンクリストを削除する関数の実装方法をわかりやすく解説

リンクリストを削除する関数とは

本記事では、C++でリンクリストの全要素を先頭から順に1つずつ解放し、リンクリスト全体を削除する関数の作成方法を解説します。

C/C++には、この操作専用の組み込み関数は用意されていません。そのため、確保したメモリはプログラマ自身が明示的に解放しなければなりません。一方、Javaでは自動ガベージコレクション(GC)が不要になったオブジェクトを自動的に回収するため、リンクリストの削除を意識する必要がありません。これは両言語のメモリ管理における大きな違いの一つです。

deleteLinkedList関数の処理の流れ

• ポインタの準備: 現在処理中のノードを指すcurrentと、次のノードを一時的に保持するnextを用意します。
• ループ処理: currentがNULLになるまで、ノードのデータを表示し、次のノードのアドレスをnextに保存してから現在のノードを解放します。
• 解放の順序が重要: 先にノードを解放すると、次のノードへたどるためのアドレス情報が失われてしまいます。必ずnextへの保存を先に行いましょう。
• 最終処理: ループ終了後、*head_refをNULLに設定し、空のリンクリストであることを明示します。

サンプルコード

#include <iostream>
using namespace std;
class Node{
    public:
    int data;
    Node* next;
};
void deleteLinkedList(Node** head_ref){
    Node* current = *head_ref;
    Node* next;
    while (current != NULL){
        cout<<current->data<<"\t";
        next = current->next;
        delete current;
        current = next;
    }
    *head_ref = NULL;
}
void push(Node** head_ref, int new_data){
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
int main(){
    Node* head = NULL;
    push(&head, 25);
    push(&head, 10);
    push(&head, 5);
    push(&head, 90);
    push(&head, 68);
    cout<<"Elements of linked list : ";
    deleteLinkedList(&head);
    cout << "\nLinked list deleted";
}

コードのポイント

push関数は新しいノードを常にリストの先頭に挿入するため、出力される要素の並びは挿入した順序と逆になります(25→10→5→90→68の順に挿入しているため、68→90→5→10→25と表示されます)。また、C++ではnewで確保したメモリはdeleteで解放するのが基本です。malloc/freeとの混用は未定義動作を引き起こす可能性があるため避けましょう。

出力結果

Elements of linked list : 68	90	5	10	25
Linked list deleted