このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
データの要素数がわからないものを扱う際、配列をそのまま使用することはで きません。 配列はあらかじめ領域を確保していなければなりません。 そのため、あらかじめ用意した領域よりも少しでもデータ量が多いと格納でき ません。
このとき、有効なのはデータ数をあとからいくらでも追加できるようなデータ 構造が必要になります。 つまり、データ数に関わらず、データ構造は一定の構造を持ち、追加、削除な どが可能になっていなければなりません。 このような要請がある場合、データの追加前と追加後で同様のデータ構造をも つことになるので、帰納的な構造がなければなりません。 つまり、データの追加を何度も繰り返したもの自体が求めるデータ構造になり ます。 つまり、データを直線状につないだ固まり自体が求めるデータ構造です。 したがって、データを追加する単位は、データを補完する部分とつなぎ合わせ る部分からなっている必要があります。
さて、線形リストとは、前回説明したような二分木です。
この二分木において、左の頂点にデータを格納することを考えると、データの 格納部分とつなぎ合わせる部分ができることになり、上記に示した可変長のデー タが格納可能なデータ構造になります。 これを、値が入る左の頂点とそうでない頂点を結合し、頂点に値が入るものと して扱った方が便利です。つまり次の図のようにして実現するのが便利です。
さて、このようなデータ構造を Java で実装します。
上記の記述において、線形リストと頂点はそれぞれオブジェクトになります。 これをここではそれぞれ SenkeiList と Choten という名前にします。 頂点は他の頂点へ接続するとともにデータを補完しますので、Generics を使 うと次のように書くことができます。
class Choten<E> {
Choten<E> next;
E data;
public Choten(){
}
public Choten(E data){
this.data = data;
}
}
public class SenkeiList<E> {
private Choten<E> head; // 管理変数
}
なお、Choten のメンバ変数は SenkeiList で操作する可能性がありますので、 private でも protected でも public でもない、同一パッケージ内でのアク セスを許す無指定にしておきます。
さて、このデータ型でデータの追加を考えます。 右の図のようにデータは追加されていきます。
ここで注目するのは赤で着色した矢印です。 一個目のデータを追加するときは管理変数を変更していますが、二個目以降は 頂点の内部の変数を変更しています。 これをプログラムで作ると、一個目と二個目で変更する変数のアクセスの方法 が変わります。
そこで、次のように、新しく作った頂点に注目している頂点のデータを移動し、 注目している頂点に入れたいデータを格納します。 このようにすると、どのような状況でも、頂点の挿入に対して、管理変数を変 更せずに頂点の操作のみで済みます。
さて、頂点を追加するのに、管理変数として、リストの最初と最後を保存し、 値は最後に追加するように作成した add を以下に示します。
class SenkeiList<E> {
private Choten<E> head,tail; // 管理変数
public SenkeiList(){
head = tail = new Choten<E>();
}
public void add(E data){
Choten<E> newnode = new Choten<E>();
tail.data = data;
tail.next = newnode;
tail = newnode;
}
}
さて、このようにして作ったリストから値を表示するには、先頭から順に data を拾っていけば良いです。 またこの場合の番兵は次の頂点を示す参照が null になっている頂点です。 したがって、次のように書くことができます。
public void show(){
Choten<E> pointer = head;
while(pointer.next!=null){
System.out.println(pointer.data);
pointer = pointer.next;
}
}
このような線形リストは可変長のデータ型として利用価値の高いものです。 特定の番号を指定したランダムアクセスは苦手ですが、任意の位置からデータ の挿入や削除が可能です。 また、データを先に入れて、先に入れたデータを先に取り出す記憶装置のこと をキュー や FIFO(First In First Out) と呼びます。 キューは相互に同期の取れていないプロセスなどでデータのやりとりをするの に活用できます。 そのため多くの通信機能で活用されています。
上で作成した線形リストは先頭から最後に向かう方向で参照が行われていまし た。 そのため、たとえ一個前の要素をアクセスしようとしても遡ることはできませ ん。 前の要素に遡れるように、逆向きの参照を加えたリストを双方向リストと呼び ます。 このデータ型は上にも下にも走査できるほか、任意の場所にデータを挿入でき ます。 そのため、テキストエディタのようなアプリケーションで使用されるデータ型 です。
上記のプログラムで一応線形リストによる可変長の記憶領域はできました。 しかし、実用的なことを考えると java.util.LinkedList のような既存のクラ スと互換性がある方が望ましいです。 そのために、 Java ではスケルトンクラスという、最小限の抽象 メソッドと、それを利用して実装された多くのメソッドが定義されたクラスが あります。
java.util.LinkedList と互換性があるようにつくるには、 java.util.AbstractSequentialList を継承し、抽象メソッドである listiterator(int n) と size() を実装すれば良いです。 但し、 listiterator(int n) は 先頭から n 番目の要素を指すイテレータを 示しますが、このイテレータも作る必要があります。
つまり、線形リストの実装においては、実際の要素のやりとりに関しては全て listIterator が担当し、リストの本体クラスは二つのメソッドしか実装する 必要が無いということです。 一方、要素のやりとりはすべて listIterator で処理します。
listIterator は java.util.ListIterator インターフェイスを実装したクラ スのオブジェクトである必要があります。 ListIterator は双方向リスト対応で、hasNext, next, hasPrevious, previous メソッドが必須です。 また、コンストラクタに番号を指定して任意の場所からアクセスを始めること ができますが、その番号も nextIndex と previousIndex で参照できます。
一方、add, set, remove もメソッドとして登録されてますので、実装しなけ ればなりません。 しかし、これに関しては書き換え不能なリストなどを扱うことも想定されてい ます。 サポートしない場合、java.lang.UnsupportedOperationException 例外を投げ ます。
さて、add, set, remove のそれぞれの実装法について検討します。 まず、add を考えます。 listIterator ではカーソルという概念があり、要素と要素の間にカーソルが 存在します。 カーソルのあとに来る要素が next で、前に来る要素が previous です。 そして、 add はそのカーソルの位置に要素を追加します。 listIterator(0) で作成されたイテレータは、先頭の要素の手前にカーソルが 来ます。 一方、 listIterator(size()) で作成されたイテレータは最後の要素の後にカー ソルが来ます。
次に、set を考えます。 set は直前に next または previous でアクセスした要素の値を書き換えます。 そのため、状態を持ち、直前に next, previous 以外が呼ばれていたら、 java.lang.IllegalStateException 例外を投げます。 直前に next, previous が呼ばれていたら、その要素を書き換えるため、 next, previous では参照した要素を覚えておく必要があります。 参照を覚えておけば、その参照に対して値を書き換えます。 なお、 set は java.util.Collections.sort を有効にするために使われます。
最後に remove を考えます。 これは set と同様にやはり直前の next, previous で参照した要素が対象に なります。 例外処理も同様です。 remove も add と同様に、注目している頂点を消すのでは無く、注目している 頂点の次の要素を値をコピーしてきて、次の要素を飛ばすようにして実装する と、管理変数の書き換えが要らなくなります。
最初の章で作成した線形リストに対して、データを先頭から削除するプログラ ムを付加しなさい。
双方向リストを作成しなさい。 データを蓄え、順に表示と逆に表示を行いなさい。
配列変数を使った記憶領域を java.util.AbstractList を継承して作成しなさ い。 また任意のテストプログラムを作成し、実際にテストを動かしなさい。