リストの仕組みを理解しよう！

プログラムで利用するリスト構造、これをコンピュータサイエンスの視点から理解しましょう。
汎用的な知識を得ることで、効率のいいコードが書けたり、別のプログラミング言語を学ぶ時の役に立ちます。

リスト (list) の概念

リストも配列と同じく複数個のデータを扱えますが実体は大きく異なります。根本的に違うのはメモリ上に連続して確保されないことでしょう。
これがリストの大きな特徴になり、配列と比べてメリットもあればデメリットも存在します。では、それらについて順番に理解しましょう。

リストとメモリの関係

さっき伝えた通り、リストはメモリ上に連続して確保されません。
1つ1つの要素は1セットごとにメモリのどこかに配置され、それをチェーンするように繋ぐのがリストです。

ここでは最もシンプルな単方向リストを例に説明します。

まず最初にリストを構築するために最低限必要なデータがあります。
それは次の要素の参照先を示す参照値です。別名でポインタやアドレス値と表現されることもあります。

この情報と自身が管理したいデータを集めたものが1要素です。そして、この1要素をノード(node)と呼びます。

ここでは次のようなデータを使いましょう。

インデックス (index) 経由のアクセス

これはプログラミング言語に依存しますが、リストも配列と同じように[]を使ってアクセスできます。
ただし、リスト構造の場合はチェーンを辿る必要があるので、後に説明するデメリットがあります。

リストのメリットとデメリット

リストの最大のメリットは後から要素を追加できることです。以前に配列は要素を追加できないと言いましたよね。
でも、リストはどうでしょう。配列と違い、確保したアドレス領域を拡大する必要がありません。
新たに生成した1要素を現在のリストに繋げば連結完了です。また、途中のチェーンを変えれば、要素間に追加することも削除することもできます。

この仕様からリストは要素数が不明な場合や頻繁に可変する場合に利用するのがベストです。
さぁ、ここまでメリットを書きましたが、対するデメリットは何でしょうか？

それは各要素へのアクセスの遅さです。それも当然、チェーンを辿らなければ要素を見つけることができません。
配列であれば、先頭アドレスからn個オフセットすれば目的のデータでしたよね。対してリストは順番に探索しないとn番目の要素にアクセスできないのです。

POINTリストは追加や削除が容易だが、配列と比べて要素に対するアクセスが遅い。

様々な種類のリスト

リストにも種類があります。有名どころを紹介するので、参考にしてください。

単方向リスト (singly linked list)

別名で片方向リストとも呼びます。先程に例として解説したリストですね。
参照値が1つなのでノードのサイズが軽量な代わり、片方向しか探索できません。

双方向リスト (doubly linked list)

全てのノードが前方と後方の参照値を持ちます。つまりは逆順に辿れます。
その代わり、後方の参照値を管理する必要があるので、ノードのサイズが増えます。

循環リスト (circular linked list)

一番最後のノードが最初のノードを指します。つまり途切れること無くチェーンします。
正直あんまり使わないんですが、どこから探索しても1周できます。

双方向循環リスト (doubly circular linked list)

全盛り。双方向に加え、どこからでも1週できます。

あとがき

リストと配列はどちらにもメリット・デメリットがあります。
自分のプログラムは何が適切か考え、最適な構造を選びましょう。

◆ コンピュータサイエンスに関する学習コンテンツ