C++で連結リスト（リンクリスト）の先頭ノードを削除する方法

連結リスト（リンクリスト）が与えられたとき、その最初の要素を削除し、新しいリストの先頭（head）へのポインタを返すプログラムを作成します。

Input : 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output : 2 -> 3 -> 4 -> 5 -> NULL

Input : 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL
Output : 4 -> 6 -> 8 -> 33 -> 67 -> NULL

この問題では、リストの最初のノードを削除し、head ポインタを2番目の要素へ移動させたうえで、新しい head を返す必要があります。

解決のためのアプローチ

この問題は非常にシンプルです。まず head ポインタを次のノードへ移動させ、その後、元の先頭だったノードのメモリを解放（free/delete）すればよいだけです。

実装例

#include <iostream>
using namespace std;
/* 連結リストのノード */
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** head_ref, int new_data) { // リストの先頭にデータを挿入
   struct 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, 12);
   push(&head, 29);
   push(&head, 11);
   push(&head, 23);
   push(&head, 8);
   auto temp = head; // temp に現在の head を保存
   head = head -> next; // head を次の要素へ移動
   delete temp; // 元の先頭ノードを削除
   for (temp = head; temp != NULL; temp = temp->next) // リストを出力
      cout << temp->data << " ";
   return 0;
}

出力結果

23 11 29 12

コードの解説

このプログラムの処理の流れは以下のとおりです。
1. 現在の head を一時変数 temp に保存します。
2. head を次のノードへ移動させます。
3. delete によって元の先頭ノードのメモリを解放します。
4. 新しい head 以降のリストを出力します。

注目すべきは計算量です。この操作にかかる時間計算量は O(1) であり、入力されるリストの長さに一切依存しません。つまり、リストがどれほど長くても一定時間で先頭ノードを削除できるため、これ以上ない最良の計算量となっています。

まとめ

本記事では、連結リストの先頭ノードを削除する問題を解決しました。具体的には、head ポインタを次の要素へ進め、古い先頭ノードを delete で解放するというアプローチを解説し、実際の C++ プログラムも示しました。この手法は C、Java、Python など他の言語でも同様に実装できます。メモリリークを防ぐために delete の呼び出しを忘れない点が重要です。本記事が皆さんの学習に役立てば幸いです。