このドキュメントは 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 になっている頂点です。 したがって、次のように書くことができます(手抜きで最後は無駄な空白がつ いてしまいます)。
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
Choten<E> pointer = head;
while(pointer.next!=null){
sb.append(pointer.data+" ");
pointer = pointer.next;
}
return sb.toString();
}
さて、この線形リストに対して、要素を一つずつアクセスすることを考えます。 既に5章で説明したように、そのためにはイテレータデザインパターンを使用 します。 Java のクラスライブラリには既にインターフェイスが組み込まれていますの で、それを使います。
package java.util;
interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
API マニュアルにある通り、next メソッドは呼び出すと順次要素を取り出し ます。 hasNext メソッドは次の要素が無いと false になります。 remove は作成してもしなくても良いメソッドですが(任意のオペレーション)、 作成する場合は、直前の next でアクセスした要素を削除するものです。
また、このイテレータを持つクラスは java.lang.Iterable インターフェイス を implement できます。 Iterable なクラスは拡張 for 文を使用することができます。
package java.lang;
interface Iterable<E> {
java.util.Iterator<E> iterator();
}
それでは上記の SenkeiList クラスに対する Iterator クラスを作成します。 要素を一個一個最初からアクセスするには、SenkeiList クラスにおける内部 の管理変数をコンストラクタで受け、それを元に next メソッドを実現するこ とにします。 next メソッドが呼ばれたときに返すべき要素を持つChoten の変数を cursor とします。
さて、remove は実装してもしなくても良いです。その場合は UnsupportedOperationException 例外を throw します。 一方、実装する場合は、API マニュアルに従います。
基になるコレクションから、反復子によって最後に返された要素を削除します (任意のオペレーション)。このメソッドは、next の呼び出しごとに 1 回だけ 呼び出すことができます。反復子の動作は、繰り返し処理がこのメソッドの呼 び出し以外の方法で実行されているときに基になるコレクションが変更された 場合は保証されません。
さらに、上記のルールに反して、next メソッドがまだ呼び出されてない場合、 または next メソッドの最後の呼び出しのあとに remove メソッドがすでに呼 び出されている場合は IllegalStateException 例外を throw します。
これを実現するには、 next メソッドでアクセスした cursor の位置を覚えて おく必要があります。 last というフィールドを作り、 next メソッドでは last に cursor を入れ ます。 一方 remove メソッドでは last の指しているデータを消しますが、これは last の指しているデータを直接消すのではなく、 last の指している Choten に cursor の指している Choten のすべてを上書 きし、 cursor が last を指すようにします。 すると、last のデータは上書きされるため無くなり、またいままで last の 位置には次の cursor が指していたデータが置かれ、その次のデータに関して は順序が保存されるため、データ順や個数は合うことになります。 また、いままで cursor の指していた Choten はどこからも参照されなくなり ます。 すると、 Java ではそのようなオブジェクトは自動的に消される対象になるた め、明示的に消去をしなくても一つ Choten オブジェクトが消えます。
以上より SenkeiListIterator を作成します。 なお、このクラスは単独で使われることはないため、 SenkeiList の内部クラ スで十分です。 なお、内部クラスのジェネリックスに関しては、既に宣言されている型引数を 再宣言しないことに注意します。
@Override
public Iterator<E> iterator() {
return new SenkeiListIterator(head);
}
class SenkeiListIterator implements Iterator<E>{
private Choten<E> cursor;
private Choten<E> last;
public SenkeiListIterator(Choten<E> head) {
cursor = head;
}
@Override
public boolean hasNext() {
return cursor.next!=null;
}
@Override
public E next() {
if(!hasNext()) throw new NoSuchElementException();
last = cursor;
E result = cursor.data;
cursor = cursor.next;
return result;
}
@Override
public void remove() {
// throw new UnsupportedOperationException();
if(last==null) throw new IllegalStateException();
last.next = cursor.next;
last.data = cursor.data;
cursor = last;
last = null;
}
}
このような線形リストは可変長のデータ型として利用価値の高いものです。 特定の番号を指定したランダムアクセスは苦手ですが、任意の位置からデータ の挿入や削除が可能です。 また、データを先に入れて、先に入れたデータを先に取り出す記憶装置のこと をキュー や 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 を継承して作成しなさ い。 また任意のテストプログラムを作成し、実際にテストを動かしなさい。