データ構造はアルゴリズムと表裏一体
同時に考えてプログラムに仕立てる

講師　矢沢　久雄

リスト構造による効率的なデータの削除と追加

図10●リスト構造 物理的には要素1～要素5の順序に並んでいるデータを任意の順序で参照できるようにする。ある1つの要素に対して次の要素が何であるかは，構造体のメンバーによって変わる。

　リスト構造は，インデックスを先頭から順番にたどるというメモリーの物理的な順序ではなく，目的に応じた順序で参照できるようにしたものである（図10[拡大表示]）。構造体のメンバーに他のデータのインデックスを持たせることで実現する。1つのデータを参照すれば，そのデータの前後に接続されたデータのインデックスを取得できる。配列の任意の位置でデータを追加および削除する処理を効率的に実行できるという特徴がある。

　もし単純な配列を利用した場合は，配列のインデックスをたどって先頭から末尾まで順番にデータを参照することしかできない。インデックスが先頭から遠く離れたデータにたどりつくまでに，途中にあるデータを無駄に参照してしまう。

図11●双方向リストと単方向リスト

　リスト構造を実現するための構造体を図11[拡大表示]に示す。構造体のメンバーに，リスト構造の1つ前のデータのインデックスを表すメンバーPrevIndexと，1つ後のデータのインデックスを表すメンバーNextIndexが定義してある（図11上）。このデータ構造は「双方向リスト」と呼ばれ，配列のリスト構造を前後にたどることができる。もしも，後方にだけにリスト構造がたどれればよいのなら，図11下に示したように構造体のメンバーにインデックスを1つだけ定義すればよい。このデータ構造は「単方向リスト」と呼ばれる。なお，リスト構造のつながり方を示すデータを「ポインタ」とも呼ぶ。

258バイトのデータ操作がたった2バイトに

図12●単純な配列を使った削除処理 要素それぞれを移動させる必要がある

　例を見てみよう。住所録の構造体Jushoを5つの要素を持った単純な配列として宣言する。ここで先頭から3つめの要素を削除する場合を考えてみよう。

　単純な配列を使った場合は先頭から3番目の要素を削除するために，それ以降の要素を順次1つずつ前に移動する必要がある（図12[拡大表示]）。4番目の要素を3番目に移動し，5番目の要素を4番目に移動する。配列の末尾は番兵を置くことで検出できるので，番兵である6番目の要素を5番目に移動して処理は終了である。先の例でも同様だが，Visual Basicの配列のインデックスは0から始まる。6番目の要素のインデックスは5となる。混乱しないように注意してほしい。

図13●リスト構造を使った削除処理 要素中のNextIndexだけ変更すればよい

　1つの要素のサイズは，3つのString型と1つのInteger型で合計86バイトとなっている＊9。単純な配列を使った場合の削除処理では，配列の3つの要素を移動するために86×3＝258バイトのデータの移動があることになる。一方，リスト構造を使った場合の削除処理では，配列の要素全体を移動することなく，削除する要素の1つ前にある要素のNextIndexメンバーだけを更新するだけで済む（図13[拡大表示]）。3番目の要素を削除する前には「2番目の要素→3番目の要素」となっていたリストを，「2番目の要素→4番目の要素」に変更するだけである。リスト構造を使った場合のデータの移動量は，2番目の要素のNextIndexメンバーに3番目の要素のNextIndexメンバーを格納するだけのわずか2バイトでよい。単純な配列を使った場合は，削除する要素の後にn個の要素があれば86×nバイトのデータ移動が必要となるが，リスト構造を使えば後にある要素の個数にかかわらず常に2バイトのデータ移動だけで済む。

　この違いを頭に入れて，数千件～数万件のデータを処理する場合を想像してみてほしい。単純な配列と比較して，リスト構造の方が処理が“軽い”こと，データの操作に対して効率のよいデータ構造であることを感じていただけることだろう。このメリットは，データを削除する場合でも同様である。