課題

C

連結リスト

１．連結リストとは

　連結リストとは、リストに含まれる各要素(セル(cell))をポインタでつないだものです。 要素はいろいろな種類のデータ型を持つデータで、個数には制限はありません。 また連結しているのですから、それらのデータの中には自分自身の要素を指すポインタが含まれます。

　データに１つの整数値を持つ連結リストは次のような構造体(自己参照構造体)の表現になります。

２．要素の挿入

　配列ではデータを挿入すると、挿入以降のデータは全て１つずつずらさなくてはなりませんが、 リストの場合は次の手順でポインタを変更することで可能となります。

　ここではポインタp で示されるセルの前に、ポインタnew で示されるセルを挿入します。
　但し、ポインタp で示されるセルの前のセルがポインタprev で示されていることにします。

• ポインタnew の示すセルの次のポインタにポインタp を代入する
  new->next = p;
• ポインタprev の示すセルの次のポインタにポインタnew を代入する
  prev->next = new;

３．要素の削除

　削除の場合も挿入と同様に、配列でデータを削除すると、削除以降のデータは全て１つずつずらさなくてはなりませんが、 リストの場合は次の手順でポインタを変更することで可能となります。

　ここではポインタp で示されるセルを削除します。
　但し、ポインタp で示されるセルの前のセルがポインタprev で示されていることにします。

• ポインタprev の示すセルの次のポインタにポインタp の示すセルの次のポインタを代入する
  prev->next = p->next;