【基本情報技術者試験】データ構造3 ～リスト～

今回は【基礎理論(アルゴリズム)編】リストについて紹介します。
この記事では、リストの特徴を学んだあとに配列との違いについても説明していきたいと思います。
配列がまだ不安な方はこちらの記事で見直しをしてから学習していきましょう！

リストについて

リストは、それぞれのデータに“次のデータへの宛先情報”を加えた状態で管理するデータ構造になっています。
宛先情報を辿ることで、1番目のデータから順番に各要素にアクセスすることができるんですね！

まずはイラストでイメージを固めておきましょう。

上のイラストのように、各要素は次のデータのアドレス(メモリ上の住所)をポインタ(宛先情報)として保持しているんですね。
また、今回のケースでは、各要素が“次の順番のデータへのポインタ”だけを保持していましたが、実はこのポインタのつけ方が異なるリストがいくつか存在しています。

次のイラストをみながら確認していきましょう。

一番上のリストは単方向リストと呼ばれるもので、それぞれのデータは次の順番のデータへのアドレスのみを保持しています。
このリストの場合は、次に進むことはできても前に戻ることができないんですね…

中段のリストは、環状リストと呼ばれるもので、基本的には単方向リストと変わりません。
しかしながら、リストの終端と先端がつながるようにポインタが設定されているので、１周して元の位置に戻ってくることができます。

一番下のリストは、双方向リストと呼ばれるもので、すべてのデータが前後のデータへのポインタを保持しています。
このリストの場合は、自由に進んだり戻ったりを繰り返すことができます。

さて、ここまででリストの特徴についての大まかな説明は終わりになります。
ここから先は配列とリストの違いについて学んでいきましょう。

配列との違いについて

配列の特徴は、“あらかじめ決められた要素数のデータ”を“メモリ上の連続した領域に格納”し、“添え字を用いてデータを管理”する事です。
リストはというと、“ポインタを用いてデータ同士を結び付ける”事で、“メモリ上のバラバラな場所にデータを保管”し、“要素数も任意に変更”できます。

ここで大切なのが、配列とリストではパフォーマンス面に差が生まれるということです。

結論からいうと、配列はデータへのアクセスに強く、リストはデータの挿入・削除に強いという特徴があります。

配列の場合、あるデータにアクセスする際には、インデックス番号を用いる事でピンポイントに要素を指定することができます。
リストの場合は、「1番目のデータ」から「目的のデータ」まで順番にポインタをたどる形でアクセスしなければならないので、
配列に比べて時間がかかります。
だから配列はリストに比べてデータのアクセスに強いんですね。

一方で、連続領域にデータを保管している配列は、要素の挿入や削除の際にデータを少しずつずらしていく作業が必要になります。
リストは、各要素をバラバラな場所に格納して宛先情報だけでデータをつなげているので、挿入や削除を素早く行うことができるんですね。

少し難しいので、次のイラストを参考にしてみてください。

配列の場合