ここでは，リスト構造について説明します。 リスト（list）は一覧と言った意味ですが，コンピュータでリスト構造とは，データの一覧を構成するデータの型のことを言います。 リストは，データが単純に一列に並んだものと考えられますが，コンピュータで操作する場合，一列に並ぶということは，一列に並んでいるように操作できると考えることも出来ます。
一列に並んだデータというと配列がすぐに思い浮かびますが，これはコンピュータ内部で実際にデータが一列に並んでいるデータ型と考えられます。似た構造ですが，少しニュアンスが違います。
配列は，コンピュータ内部のメモリーでのデータの並びを言語で操作出来るようにしたもので，分かりやすいものですが，これだけではいくつかの弱点を持っています。 例えば，
と並んでいる配列で A(2) と A(3) の間に 1 というデータを挿入して
とするには，A(3) 以下のデータをすべて１つづらして，A(3) を空けて，そこに1 を入れることになります。この処理はデータが多いと負荷のある処理になります。また逆に，上のデータで A(2) の 4 を削除して
とするには，A(3) 以下のデータをすべてずらす必要があります。 このような処理はデータ数が少なくて，こういった挿入・削除の回数が少なければ，たいした負荷にはなりませんが，場合によってはかなりの負荷になることもあります。 例えば，住所録などのデータベースでデータの部分が大きいと，データの移動は負荷が掛かります。このデータの追加と削除を容易にした方式がリスト型と考えることも出来ます。
リストは，実態として一列に並んでいなくても，一列に並んでいるように操作できるように工夫したデータ型です。これは各々のデータを独立なものと考え，データにリンクを付けてその順で順番を考えると言うものです。 例えば，
のようにデータとそのリンク（今の場合→）があったとします。ここでデータｂと データc の間に データeを挿入するとします。この場合，最後の位置にデータeを付け加え，リンクを付け替えます。
このようにすると，元のデータは移動の必要がありません。 また，
で，データcを削除するとします。この場合もリンクを付け替えて，
とします。このようにすると，元のデータは移動の必要がありません。 データ間のリンクは複雑そうに見えますが，実はそうではありません。以下にその方法を説明します。
リスト構造は，配列変数を使うことで，比較的簡単に実現できます。 どのようなデータを格納するかによって，色々なリスト構造が出来ますが，その作り方は基本的には大体同じですので，ここでは 双方向リストといわれるものの簡単なものを作成してみます。 まず，リストデータを格納するための配列の組とヘッドとテイルを宣言します。例えば Public Head, Tail, NDN(100), PDN(100), LData$(100), ITop としましょう。これはリストデータに最大100個の文字列を格納するための LData$ という配列変数，および リンクのための配列変数 NDN と PDN，および リストデータの先頭を示す Head， 最後を示す Tail，挿入の場合の位置を示す ITopを宣言しています。サブプログラムや関数の中でも使えるよう Public 宣言をしています。 構造体などのユーザー定義型が使える言語では，NDN, PDN, LData$ は一括して定義することが出来ますが，現在の Tiny Basic では出来ないので，配列変数の組として実現します。 実現の方法は，配列変数が下図のように配置されていると見ると分かりやすいでしょう。
これは上の説明の例を表にしたものです。 Head = 1 は先頭データが１番にあることを示します。また，Tail=4 は４番データが最終データであることを示しています。また，ITop=5はこれからデータ追加がある場合，５番に追加することを示しています。 NDN はNext Data Number 即ち，次のデータへのリンクです。１番のデータのNDN=2ですから，次のデータは２番のデータであることを示しています。同様に，２番のデータの次のデータは３番のデータです。４番のデータの NDN=0 はここではこれが最後のデータであることを示しています。Tail=4 に対応しています。 PDN は Previous Data Number 即ち，１つ前のデータへのリンクです。最後のデータ４番のPDN=3 より，その１つ前のデータは３番データであることを示しています。１番のデータの PDN=0 はこれが最初のデータであることを示しています。
上のデータのデータbとデータc の間にデータeを挿入してみます。この場合，
となります。 実際のデータは５番に書き込みます。そして，データbの次のデータを示す NDNを5にします。５番データの次のデータはデータcですから，NDN=3 です。また５番データの前のデータはデータｂですから，PDN=2となります。また，データcの前のデータはデータeですから，３番の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 ２～４行が追加するデータをITop番に書き込みます。 ５行でPt番のデータの NDN を書き込んだデータの番号にします。 ６行で元々のPt番のデータの次のデータの前のデータを新たに追加したデータにします。 ８行の「次のITop を決める」は場合に応じた方法が考えられます。使用していない番号を求める効率的方法は複雑ですが，一番簡単な方法は， ITop = ITop + 1 とする方法です。
今度は上の例でデータbを削除してみましょう。この場合，
となります。 ここでは、データの削除は実際には行わず、リンクの付け替えをしているだけです。 Head からリンクを辿っていくと２番のデータは飛び越して現れません。 実際にデータの削除をしていないので、２番のデータが使用しているかどうかは最初から辿っていってそこへのリンクがないということからしか分かりません。使用しているかどうかの判定は、ITop の決定と関係しています。これをメモリを節約して一杯に使う場合は、使用中かどうかの判定をするフラグを用意して、それに従って、 ITop を決めることもできます。 この処理を行う，Sub プログラムは例えば，次のように書けます。このSubプログラムはPt番のデータを削除（実際はリンクの付け替え）を行います。 01 Sub DelList(Pt) 03 NDN(PDN(Pt)) = NDN(Pt) 04 PDN(NDN(Pt)) = PDN(Pt) 05 End Sub ３行が Pt 番のデータの前のデータの NDN をPt 番の次のデータに書き換えます。 ４行で 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 とすると、逆順に表示されます。
このリスト構造を使って１つのプログラムを作ってみました。List.tbtです。 このプログラムは英文のテキストファイルを読み込んで、そこに現れる単語の一覧をアルファベット順で使用回数と共に表示するものです。 ファイルから単語を順次読み込み、その単語がリストにあれば、回数を加え、無ければリストに加えるものです。リストが、アルファベット順になるように単語を加える場所を決定してから、リストに加えます。 加える場所を決定するのに基本的に線形探索を使っていますから、高速ではありませんが、比較的短時間に処理します。例として処理したテキストはt.txtです。
リスト構造は配列変数の使い方を少し工夫したものですが，多くの場面で使われます。 例えば、ディスクにファイルを格納する方法もこのリスト構造の考えが使われています。 実体を操作するのではなく，それを指し示すリンクを処理することで，実体を処理したかのように見えるという考えは示唆に富む考えです。
|