Web教材一覧ハードウェアとソフトウェア

リスト構造

キーワード

リスト構造、連結リスト、ポインタ、リスト要素の削除・挿入


リスト構造の概念

配列
同一の構造を持つデータに、単一の名称をつけたデータ構造を配列(Array)といい、個々のデータを要素といいます。各要素は A(1)、A(2) のように、「配列名(添字の値)」の形式で示します。
 配列では、要素間の情報を示すことはできません。一般には、各要素の値と添字の値は無関係です。そのため、要素を昇順(小さい順)に処理するときには、事前にソートを行っておく必要があります。
リスト構造とポインタ(「連結リスト(単方向)」参照)
リスト構造とは、データ要素と、他のデータの格納位置を指すポインタを要素として持つデータ構造のことです。
 上の「連結リスト(単方向)」では、要素を昇順に並べたときに、自分の次になる要素(自分の次に大きな要素)の添字の値がポインタに入れてあります。例えば、AAAのポインタは4なので、AAAの次に大きい要素が A(4)=BBBであり、BBBのポインタの2から、その次の要素が A(2)=DDD であることを示しています(最後(最大)の要素 FFF のポインタが0なのは、この要素の後の要素がないことを示しています)。
 このようにポインタを設定しておけば(そして、最小値が先頭にあることを前提にすれば)、ポインタを参照することにより、昇順に処理することが容易になります。
複数のポインタ(「連結リスト(双方向)」参照)
一つの要素に複数のポインタを設定することができます。上の「連結リスト(双方向)」では、右側のポインタでは昇順を、左側のポインタでは降順(大きい順)を与えています。これにより、昇順の処理も降順の処理も容易に行うことができます。また、「単方向」の場合は、「最小値が先頭にあることを前提」にしていましたが、「双方向」のポインタがあれば、最初に1度だけ、右側のポインタが0である要素を探索すればよいので、このような前提が不要になります。
 ポインタは、大小関係でなく、発生順序など順序に関係する事項ならば、どのようなものにもつけられます。また、工夫をすることにより、同じグループに属するものだけを取り出すことにも利用できます。そのため、データベースでの基本的な考え方につながります。

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

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

削除処理(要素 DDD の削除)
DDD を削除するということは、その直前の BBB の次が EEE になればよいのですから、BBB のポインタを EEE を指すように変更する(2だったのを5にする)だけで終了します。
  1. DDDを探索して、DDD の添字の値(2)を知る。
  2. 2をポインタの値が2である要素を探索する。BBBだとわかる。
  3. BBB のポインタの値(2)をDDDのポインタの値(5)に置き換える。
 このとき、要素 DDD を実際に消去するかどうかは、データ保管容量の問題であり、リスト構造そのものには影響を与えません。そのままにしておくことにより、復元することも容易になります。
挿入処理(要素 CCC の挿入)
新しい要素 CCC を、BBBとDDDの間に挿入する場合を考えます。直前の BBB のポインタを CCC が置かれる位置(ここでは6)にし、CCC のポインタは、いままで BBB のポインタが持っていた値(2)にすれば、処理が終了します。
  1. CCC を任意の場所(ここでは6)に書き込む。
  2. 昇順探索により、CCC が BBB の次になることを知る。
  3. CCC のポインタの値に、BBB のポインタの値(2)を書き込む。
  4. BBB のポインタに、CCC を書きこんだ場所(6)を書きこむ。