リスト構造について

 ここでは,リスト構造について説明します。

 リスト(list)は一覧と言った意味ですが,コンピュータでリスト構造とは,データの一覧を構成するデータの型のことを言います。

  リストは,データが単純に一列に並んだものと考えられますが,コンピュータで操作する場合,一列に並ぶということは,一列に並んでいるように操作できると考えることも出来ます。

 一列に並んだデータというと配列がすぐに思い浮かびますが,これはコンピュータ内部で実際にデータが一列に並んでいるデータ型と考えられます。似た構造ですが,少しニュアンスが違います。
 

配列の性質

 配列は,コンピュータ内部のメモリーでのデータの並びを言語で操作出来るようにしたもので,分かりやすいものですが,これだけではいくつかの弱点を持っています。

 例えば,

A(1) 8
A(2) 4
A(3) 7
・・・  

と並んでいる配列で A(2) と A(3) の間に 1 というデータを挿入して

A(1) 8
A(2) 4
A(3) 1
A(4) 7
・・・  

とするには,A(3) 以下のデータをすべて1つづらして,A(3) を空けて,そこに1 を入れることになります。この処理はデータが多いと負荷のある処理になります。また逆に,上のデータで A(2) の 4 を削除して

A(1) 8
A(2) 1
A(3) 7
・・・  

とするには,A(3) 以下のデータをすべてずらす必要があります。

 このような処理はデータ数が少なくて,こういった挿入・削除の回数が少なければ,たいした負荷にはなりませんが,場合によってはかなりの負荷になることもあります。

 例えば,住所録などのデータベースでデータの部分が大きいと,データの移動は負荷が掛かります。このデータの追加と削除を容易にした方式がリスト型と考えることも出来ます。

リストの考え

 リストは,実態として一列に並んでいなくても,一列に並んでいるように操作できるように工夫したデータ型です。これは各々のデータを独立なものと考え,データにリンクを付けてその順で順番を考えると言うものです。

例えば,

データa

データb

データc

データd

   

のようにデータとそのリンク(今の場合→)があったとします。ここでデータbと データc の間に データeを挿入するとします。この場合,最後の位置にデータeを付け加え,リンクを付け替えます。

       
             

データa

データb

 

データc

データd

 

データe

             
   

このようにすると,元のデータは移動の必要がありません。

 また,

データa

データb

データc

データd

データe

で,データcを削除するとします。この場合もリンクを付け替えて,

データa

データb

 

データc

 

データd

データe

             
       

とします。このようにすると,元のデータは移動の必要がありません。

 データ間のリンクは複雑そうに見えますが,実はそうではありません。以下にその方法を説明します。

リストの実現方法

 リスト構造は,配列変数を使うことで,比較的簡単に実現できます。

 どのようなデータを格納するかによって,色々なリスト構造が出来ますが,その作り方は基本的には大体同じですので,ここでは 双方向リストといわれるものの簡単なものを作成してみます。

 まず,リストデータを格納するための配列の組とヘッドとテイルを宣言します。例えば

Public Head, Tail, NDN(100), PDN(100), LData$(100), ITop

としましょう。これはリストデータに最大100個の文字列を格納するための LData$ という配列変数,および リンクのための配列変数 NDN と PDN,および リストデータの先頭を示す Head, 最後を示す Tail,挿入の場合の位置を示す ITopを宣言しています。サブプログラムや関数の中でも使えるよう Public 宣言をしています。

 構造体などのユーザー定義型が使える言語では,NDN, PDN, LData$ は一括して定義することが出来ますが,現在の Tiny Basic では出来ないので,配列変数の組として実現します。

 実現の方法は,配列変数が下図のように配置されていると見ると分かりやすいでしょう。

NDN PDN LData$
1 2 0 データa
2 3 1 データb
3 4 2 データc
4 0 3 データd
5      

Head

Tail

ITop

1

4

5

 これは上の説明の例を表にしたものです。


 Head = 1 は先頭データが1番にあることを示します。また,Tail=4 は4番データが最終データであることを示しています。また,ITop=5はこれからデータ追加がある場合,5番に追加することを示しています。

NDN はNext Data Number 即ち,次のデータへのリンクです。1番のデータのNDN=2ですから,次のデータは2番のデータであることを示しています。同様に,2番のデータの次のデータは3番のデータです。4番のデータの NDN=0 はここではこれが最後のデータであることを示しています。Tail=4 に対応しています。

PDN は Previous Data Number 即ち,1つ前のデータへのリンクです。最後のデータ4番のPDN=3 より,その1つ前のデータは3番データであることを示しています。1番のデータの PDN=0 はこれが最初のデータであることを示しています。

データの挿入

 上のデータのデータbとデータc の間にデータeを挿入してみます。この場合,

NDN PDN LData$
1 2 0 データa
2 5 1 データb
3 4 5 データc
4 0 3 データd
5 3 2 データe

Head

Tail

ITop

1

4

6

となります。

 実際のデータは5番に書き込みます。そして,データbの次のデータを示す NDNを5にします。5番データの次のデータはデータcですから,NDN=3 です。また5番データの前のデータはデータbですから,PDN=2となります。また,データcの前のデータはデータeですから,3番のPDN=5になります。


この処理を行う,Sub プログラムは例えば,次のように書けます。このSubプログラムはpt番の次にD$を追加します。行番号を付けて説明します。

01  Sub AddList(D$,Pt)
02     LData$(ITop)   = D$
03     NDN(ITop)      = NDN(Pt)
04     PDN(ITop)      = Pt
05     NDN(Pt)        = ITop
06     PDN(NDN(ITop)) = ITop
07  
08     次のITop を決める
09  
10  End Sub

2〜4行が追加するデータをITop番に書き込みます。

5行でPt番のデータの NDN を書き込んだデータの番号にします。

6行で元々のPt番のデータの次のデータの前のデータを新たに追加したデータにします。

8行の「次のITop を決める」は場合に応じた方法が考えられます。使用していない番号を求める効率的方法は複雑ですが,一番簡単な方法は,

ITop = ITop + 1

とする方法です。

データの削除

 今度は上の例でデータbを削除してみましょう。この場合,

NDN PDN LData$
1 5 0 データa
2 5 1 データb
3 4 5 データc
4 0 3 データd
5 3 1 データe

Head

Tail

ITop

1

4

6

となります。

 ここでは、データの削除は実際には行わず、リンクの付け替えをしているだけです。

 Head からリンクを辿っていくと2番のデータは飛び越して現れません。

 実際にデータの削除をしていないので、2番のデータが使用しているかどうかは最初から辿っていってそこへのリンクがないということからしか分かりません。使用しているかどうかの判定は、ITop の決定と関係しています。これをメモリを節約して一杯に使う場合は、使用中かどうかの判定をするフラグを用意して、それに従って、 ITop を決めることもできます。


この処理を行う,Sub プログラムは例えば,次のように書けます。このSubプログラムはPt番のデータを削除(実際はリンクの付け替え)を行います。

01  Sub DelList(Pt)
03     NDN(PDN(Pt))   = NDN(Pt)
04     PDN(NDN(Pt))   = PDN(Pt)
05  End Sub

3行が Pt 番のデータの前のデータの NDN をPt 番の次のデータに書き換えます。

4行で Pt番のデータの次のデータの PDN を Pt番の前のデータに書き換えます。

リストデータの表示

リストデータの一覧を表示するには、例えば

i=Head
While NDN(i)>0
   Print LData$(i)
   i=NDN(i)
Wend

とすると、正順に表示され,

i=Tail
While PDN(i)>0
   Print LData$(i)
   i=PDN(i)
Wend

とすると、逆順に表示されます。

応用例

 このリスト構造を使って1つのプログラムを作ってみました。List.tbtです。

 このプログラムは英文のテキストファイルを読み込んで、そこに現れる単語の一覧をアルファベット順で使用回数と共に表示するものです。

 ファイルから単語を順次読み込み、その単語がリストにあれば、回数を加え、無ければリストに加えるものです。リストが、アルファベット順になるように単語を加える場所を決定してから、リストに加えます。

 加える場所を決定するのに基本的に線形探索を使っていますから、高速ではありませんが、比較的短時間に処理します。例として処理したテキストはt.txtです。

 

まとめ

 リスト構造は配列変数の使い方を少し工夫したものですが,多くの場面で使われます。

例えば、ディスクにファイルを格納する方法もこのリスト構造の考えが使われています。

 実体を操作するのではなく,それを指し示すリンクを処理することで,実体を処理したかのように見えるという考えは示唆に富む考えです。