リスト構造

リスト構造の概念

配列

同一の構造を持つデータに、単一の名称をつけたデータ構造を配列（Array）といい、個々のデータを要素といいます。各要素は Ａ(１)、Ａ(２) のように、「配列名(添字の値)」の形式で示します。
　配列では、要素間の情報を示すことはできません。一般には、各要素の値と添字の値は無関係です。そのため、要素を昇順（小さい順）に処理するときには、事前にソートを行っておく必要があります。

リスト構造とポインタ（「連結リスト（単方向）」参照）

リスト構造とは、データ要素と、他のデータの格納位置を指すポインタを要素として持つデータ構造のことです。
　上の「連結リスト（単方向）」では、要素を昇順に並べたときに、自分の次になる要素（自分の次に大きな要素）の添字の値がポインタに入れてあります。例えば、ＡＡＡのポインタは４なので、ＡＡＡの次に大きい要素が Ａ(４)＝ＢＢＢであり、ＢＢＢのポインタの２から、その次の要素が Ａ(２)＝ＤＤＤ であることを示しています（最後（最大）の要素 ＦＦＦ のポインタが０なのは、この要素の後の要素がないことを示しています）。
　このようにポインタを設定しておけば（そして、最小値が先頭にあることを前提にすれば）、ポインタを参照することにより、昇順に処理することが容易になります。

複数のポインタ（「連結リスト（双方向）」参照）

一つの要素に複数のポインタを設定することができます。上の「連結リスト（双方向）」では、右側のポインタでは昇順を、左側のポインタでは降順（大きい順）を与えています。これにより、昇順の処理も降順の処理も容易に行うことができます。また、「単方向」の場合は、「最小値が先頭にあることを前提」にしていましたが、「双方向」のポインタがあれば、最初に１度だけ、右側のポインタが０である要素を探索すればよいので、このような前提が不要になります。
　ポインタは、大小関係でなく、発生順序など順序に関係する事項ならば、どのようなものにもつけられます。また、工夫をすることにより、同じグループに属するものだけを取り出すことにも利用できます。そのため、データベースでの基本的な考え方につながります。

リスト構造での要素の削除、挿入処理

データをリスト構造にする大きな目的に、要素を削除したり挿入する処理が容易になることがあげられます。それを、「連結リスト（単方向）」でのデータを用いて説明します。

削除処理（要素 ＤＤＤ の削除）

ＤＤＤ を削除するということは、その直前の ＢＢＢ の次が ＥＥＥ になればよいのですから、ＢＢＢ のポインタを ＥＥＥ を指すように変更する（２だったのを５にする）だけで終了します。

1. ＤＤＤを探索して、ＤＤＤ の添字の値（２）を知る。
2. ２をポインタの値が２である要素を探索する。ＢＢＢだとわかる。
3. ＢＢＢ のポインタの値（２）をＤＤＤのポインタの値（５）に置き換える。

　このとき、要素 ＤＤＤ を実際に消去するかどうかは、データ保管容量の問題であり、リスト構造そのものには影響を与えません。そのままにしておくことにより、復元することも容易になります。

挿入処理（要素 ＣＣＣ の挿入）

新しい要素 ＣＣＣ を、ＢＢＢとＤＤＤの間に挿入する場合を考えます。直前の ＢＢＢ のポインタを ＣＣＣ が置かれる位置（ここでは６）にし、ＣＣＣ のポインタは、いままで ＢＢＢ のポインタが持っていた値（２）にすれば、処理が終了します。

1. ＣＣＣ を任意の場所（ここでは６）に書き込む。
2. 昇順探索により、ＣＣＣ が ＢＢＢ の次になることを知る。
3. ＣＣＣ のポインタの値に、ＢＢＢ のポインタの値（２）を書き込む。
4. ＢＢＢ のポインタに、ＣＣＣ を書きこんだ場所（６）を書きこむ。

プログラムと操作

双方向ポインタをもつリスト構造の挿入・削除のプログラムおよびその操作は、「双方向ポインタのプログラム」にあります。