C言語で学ぶ連結リストの先頭(ヘッド)・末尾(テール)要素の削除ロジック

連結リスト(リンクリスト)は動的メモリ割り当てを使用するデータ構造であり、要素の増減に応じてサイズが柔軟に変化します。連結リストは複数の「ノード」の集合体として表現されます。

各ノードは次の2つの部分で構成されています。

• データ部(ele):実際に格納される値
• リンク部(next):次のノードを指すポインタ

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

連結リストに対して行われる操作は、主に以下の3種類です。

• 挿入(Insertion)
• 削除(Deletion)
• 走査(Traversing)

削除処理の基本手順

連結リストからノードを削除する際は、一般的に次の手順に従います。

1. 削除対象のノードを特定する。
2. ノードを解放してもリストが分断されないように、リンク(ポインタ)を適切に調整する。
3. 削除する要素を表示または返却する。
4. メモリを解放する。

先頭要素(ヘッド)の削除

C言語で先頭要素を削除するには、以下のコードのように実装します。

1. void del_head()
2. {
3.    int x;
    Node *temp;
4.    if(Head==NULL)
5.    {
6.       printf("List is empty");
7.       return;
8.    }
9.    x=Head->ele;
10.   temp=Head;
11.   if(Head==Tail)
12.      Head=Tail=NULL;
13.   else
14.      Head=Head->next;
15.   printf("Deleted element %d",x);
16.   free(temp);
17. }

コードのポイントを順に見ていきましょう。

• ステップ4:リストが空かどうかをチェックします。
• ステップ9:削除対象の要素を読み取ります。
• ステップ10:一時ポインタtempが先頭ノード(Head)を参照します。
• ステップ11〜12:最後の1要素の削除かどうか(先頭と末尾が同じノードか)を判定し、該当する場合はHeadとTailを両方NULLにします。
• ステップ14:Headポインタを次の要素へ移動させます。
• ステップ15:削除した要素を表示します。
• ステップ16:不要になったノードのメモリを解放します。

末尾要素(テール)の削除

続いて、C言語で末尾要素を削除する場合の実装例です。

1. void del_tail()
2. {
3.    int x;
4.    Node *temp;
5.    if(Head==NULL)
6.    {
7.       printf("List is empty");
8.       return;
9.    }
10.   temp=Head;
11.   while(temp->next != Tail)
12.      temp=temp->next;
13.   x=Tail->ele;
14.   Tail=temp;
15.   temp=temp->next;
16.   Tail->next=NULL;
17.   printf("Deleted element %d",x);
18.   free(temp);
19. }

こちらも処理の流れを確認しておきましょう。

• ステップ5:リストが空かどうかをチェックします。
• ステップ10〜12:一時ポインタtempを、末尾から2番目のノードまで移動させます。
• ステップ13:削除対象となる末尾の要素を読み取ります。
• ステップ14:Tailポインタを末尾から2番目のノードへ移動させます。
• ステップ15:一時ポインタtempを現在の末尾ノードへ移動させます。
• ステップ16:新しい末尾ノードのnext参照をNULLにすることで、旧末尾ノードへのリンクを切断します。
• ステップ17:削除した要素を表示します。
• ステップ18:不要になったノードのメモリを解放します。

このように、先頭の削除はO(1)で高速に行える一方、単方向連結リストでは末尾の削除に末尾から2番目のノードを探す走査が必要となり、計算量はO(n)になります。双方向連結リストを使えば末尾の削除も効率化できるため、用途に応じたデータ構造の選択が重要です。