応用情報｜リストの仕組みをわかりやすく解説！要素の追加や削除の方法は？配列と何が違うの？

「要素の追加や削除ってなに？」

「ポインタを参照する回数が多いってどういうこと？」

こんな悩みをすっきり解決できるように、わかりやすく解説していきます！

こちらの記事もぜひご覧ください。

連結リストってなに？

順番に並べられたデータのことを「リスト」と呼びます。リストには主に「配列」と「連結リスト」の２種類があり、今回解説するのは「連結リスト」のほうです。

プログラミングなどを学んでいる方は「配列」のイメージをしやすいかと思います。しかし、「連結リスト」のほうのイメージや詳細が掴みづらいという人も多いので、仕組みをしっかり理解しておきましょう。

連結リスト（以下、リスト）には、３つの種類があります。

それぞれの要素には住所のようなものがあります。配列でいう添え字のようなものです。それを指し示すのがポインタで、それぞれの要素が前や後ろの要素を指すポインタを持つことで要素同士がつながっているのです。

つまり、ポインタの値を消去してしまうと、「次のデータは何だっけ・・・？」となり、要素同士のつながりが途切れてしまいます。

リストの特徴は、記憶装置上のそれぞれの要素の位置が固定されていないことです。

リストは、記憶装置上ではこのように管理されています。リストとして並んでいる順番とは全く違い、ばらばらに置かれていますよね。なので、記憶装置上のデータでは「このデータはリスト上では前から何番目なんだろう・・・？」というのは全く分かりません。

このような性質上、リストではピンポイントに「前から３番目のデータ！」と指定することができません。データにたどり着くためには、前もしくは後ろから順番に、地道に辿っていくしかありません。

そう考えると「めんどくさいじゃん！」「配列のほうが便利じゃん！」と思うかもしれませんが、リストにも長所があります。それは、データの追加、削除が容易なことです。

配列だと、前から２番目にデータを追加したいとき、３番目以降のデータを１個ずつ後ろにずらし、隙間を空けてからデータを追加しなければなりませんよね。しかしリストでは、ポインタの値を操作することで簡単にデータを追加することができるのです。

その方法を詳しく説明していきます。

試験でよく出題される形式は、「先頭要素へのポインタ」と「末尾要素へのポインタ」を持ったリストです。濃いブラウンの部分がポインタ、白い部分がその要素のアドレスだと思ってください。

「head」のポインタが示すのが先頭の要素、「tail」が末尾の要素です。

要素の追加は、先頭で行っても、末尾で行っても処理量が同じです。

先頭に要素を追加する場合
① 新しく追加する要素のポインタに、headのポインタ「０」を設定する
② headのポインタに、新しく追加する要素のアドレスを設定する

末尾に要素を追加する場合
① tailから辿った先にあるアドレス４の要素のポインタに、新しい要素のアドレスを設定する
② tailに新しい要素のアドレスを設定する

ポインタの値を変更することで、要素同士の結びつきのルートを容易に変更できます。また、ポインタは上書き保存ですので、新しい結びつきを作りたいときに、わざわざ元の結びつきを削除するなどはしなくても大丈夫です。

要素の削除は、末尾の処理量が先頭の処理量よりも多くなります。

先頭の要素を削除する場合
① headのポインタの値を、headから辿ったアドレス１の要素のポインタの値に変更する

末尾の要素を削除する場合
① headから辿り、後ろから２番目の要素を見つける
② 後ろから２番目の値のポインタをNULLにする
③ tailのポインタの値を、後ろから２番目の要素のアドレスに設定する

tailを使うことで、末尾の要素へアクセスすることは可能です。しかし、単方向リストや循環リストの場合、自分の前の要素へ辿っていくことはできません。そのため、後ろから２番目へアクセスするためには、前から順番に辿っていくしかないのです。

連結リストについては理解できたでしょうか。特に、挿入や削除の際の処理量についてはよく問われる内容ですので、イメージを掴んでおきましょう！想像しづらいときは、画像のように図を描いてみるのがおすすめです。苦手意識を持たずに問題を解けるようになれるよう、一緒に頑張りましょう！