●はじめに
前回はインターフェースと例外処理について説明しました。今回はオブジェクト指向機能を使った簡単な例題として、連結リスト (linked list) という基本的なデータ構造を作成します。
連結リストを扱うプログラミング言語といえば Lisp が有名です。このほかに、関数型言語 (SM/NJ, OCaml, Haskell など) や論理型言語の Prolog も、組み込みのデータ構造として連結リストを装備しています。また、Java のパッケージにも連結リストと同等の機能を持つクラス LinkedList が用意されているので、わざわざ連結リストを自作する必要はまったくありません。今回は Java のお勉強ということで、あえて連結リストをプログラムしてみましょう。
●連結リストの構造
今回取り上げる連結リストはデータを一方向 [*1] につないだデータ構造です。図 1 に連結リストの構造を示します。
図 1 : 連結リストの構造
連結リストはセル (cell) というデータをつなげて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。図 1 でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへの参照を格納します。リストの終わりを示すため、最後のセルの右側には特別な値 (null) を格納します。
null は「なにも無い」ことを表す特別なデータ (null 型) です。null はクラスなどの参照データ型に無条件でキャストすることができます。たとえば、オブジェクトを格納する変数や配列は、デフォルトで null が初期値になります。
そして、図 1 (1) のように先頭セルへの参照を変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、図 1 (2) のようにヘッダセルを用意する方法もあります。
連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータになるほどアクセスに時間がかかります。これが連結リストの短所です。
[*1] 一方向につないだ連結リストを「片方向リスト (singly-linked list)」といいます。これに対し、前後のセルをつないだ「双方向リスト (doubly-linked list)」という連結リストもあります。Java の LinkedList クラスは双方向リストです。
●クラスの定義
それではプログラムを作りましょう。最初に、連結リストを表すクラス SinglyLinkedList とセルを表すクラス Cell を定義します。リスト 1 を見てください。
リスト 1 : 連結リストの定義
// セル
class Cell {
// フィールド変数
private Object value;
private Cell link;
// コンストラクタ
Cell(Object obj, Cell xs) {
value = obj;
link = xs;
}
// アクセスメソッド
Object getValue() { return value; }
Cell getLink() { return link; }
void setValue(Object obj) { value = obj; }
void setLink(Cell xs) { link = xs; }
}
// 連結リスト
class SinglyLinkedList {
// フィールド変数
private Cell head;
private int size;
// コンストラクタ
SinglyLinkedList() {
head = new Cell(null, null); // ヘッダーセル
size = 0;
}
// メソッドの定義
...
}
Cell のフィールド変数 value にデータを格納し、link に次のセルへの参照を格納します。value のデータ型は Object とします。Java のクラスは必ず Object を継承するので、どんなクラスのオブジェクトでもアップキャストすることで連結リストに格納することができます。あとは、コンストラクタとアクセスメソッドを定義します。これらのメソッドを使ってセルを操作します。
次に、セルを使って連結リストクラス SinglyLinkedList を作成します。このクラスにはセルを保持するフィールド変数 head とデータの個数をカウントする変数 size を用意します。コンストラクタで、head にヘッダセルをセットし、size を 0 に初期化します。ヘッダセルの value はダミーで、このプログラムでは null をセットします。また、後ろのセルは無いので link にも null をセットします。
●連結リストの操作メソッド
次は、連結リストを操作するメソッドを定義します。基本的なメソッドを表 1 に示します。
| メソッド | 機能 |
|---|---|
| Object get(int n) | n 番目の要素を求める |
| void insert(int n, Object x) | n 番目の位置にデータ x を追加する |
| Object remove(int n) | n 番目の要素を削除する |
| Object set(int n, Object x) | n 番目の要素をデータ x に置き換える 返り値は置き換えられた古い要素を返す |
| void clear() | 連結リストを空にする |
| int size() | 要素の個数を返す |
| boolean isEmpty() | 空リストであれば true を返す |
要素の位置は配列と同様に 0 から数えることにします。位置 n がリストの長さよりも大きい場合、どのメソッドでも例外を送出することにします。
リスト 2 : 例外クラス
class ListIndexOutOfBoundsException extends IndexOutOfBoundsException {
public ListIndexOutOfBoundsException() { }
public ListIndexOutOfBoundsException(String msg) { super(msg); }
}
例外の名前は ListIndexOutOfBoundsException とし、IndexOutOfBoundsException を継承することにします。
●作業用メソッド nth()
最初に、作業用のメソッドとして n 番目のセルを求める処理を作ります。メソッド名は nth() としました。リスト 3 を見てください。
リスト 3 : n 番目のセルを求める
private Cell nth(int n) {
int i = -1;
Cell xs = head;
while (xs != null) {
if (n == i) return xs;
i++;
xs = xs.getLink();
}
throw new ListIndexOutOfBoundsException("SinglyLinkedList");
}
nth() は private メソッドに設定します。最初に、ヘッダセルを xs にセットします。ヘッダセルから数えるので、変数 i は -1 に初期化します。次に、while ループでセルをたどり、i が n と等しくなったとき、そのセルを return で返します。
セルのたどり方は実に簡単です。図 2 を見てください。
(1) xs = xs.getLink() => xs2 (2) xs = xs.getLink() => xs3 図 2 : セルのたどり方
セル xs1 の link にはセル xs2 への参照が格納されています。変数 xs が xs1 を指している場合 (図 2 (1))、xs の値を xs.getLink() の返り値で更新すれば、xs の値はセル xs2 になります (図 2 (2))。さらに xs の値を xs.getLink() の返り値で更新すれば、xs の値は xs3 になります (図 2 (3))。
nth() の場合、while ループでセルをたどっていきますが、途中でセルがなくなった場合、xs の値は null になります。ここで while ループを終了して、例外 ListIndexOutOfBoundsException を送出します。
●データの取得
それでは、n 番目の要素を求めるメソッド get() から作りましょう。リスト 4 を見てください。
リスト 4 : n 番目の要素を求める
public Object get(int n) {
return nth(n).getValue();
}
nth() を呼び出して n 番目のセルを求め、格納されているデータを getValue() で求めるだけです。
●データの挿入
次は、データを挿入するメソッド insert() を作りましょう。データの挿入はセルの link を書き換えることで実現できます。図 3 を見てください。セル xs1 とセル xs2 の間に、セル xs4 を挿入します。
図 3 : データの挿入
セル xs1 の後ろにセル xs4 を挿入する場合、セル xs1 の link にはセル xs2 への参照がセットされているので、この値をセル xs4 の link にセットします。これで、セル xs4 とセル xs2 がリンクされます。次に、セル xs1 の link にセル xs4 への参照をセットします。これで、セル xs1 とセル xs2 の間に、セル xs4 を挿入することができます。
プログラムをリスト 5 に示します。
リスト 5 : データの挿入
public void insert(int n, Object obj) {
Cell xs = nth(n - 1);
Cell ys = new Cell(obj, xs.getLink());
xs.setLink(ys);
size++;
}
連結リストにデータを挿入する場合、挿入する位置のひとつ手前のセルが必要になります。nth() で n - 1 番目のセルを求めます。セル xs が見つかれば、xs の後ろに obj を挿入します。n が 0 の場合、nth() はヘッダセルを返すので、リストの先頭にデータが挿入されることになります。
new Cell(obj, xs.getLink()) で obj を格納する新しいセル ys を生成します。第 2 引数に xs.getLink() を指定することで、新しいセルの後ろに、xs の後ろのセルを接続することができます。そして、xs.setLink(ys) で xs の link を新しいセル ys に書き換えます。これで xs の後ろに ys を挿入することができます。最後に size を +1 します。
●データの削除
次は、データを削除するメソッド remove() を作りましょう。
図 4 : データの削除
データを削除する場合も、セルを付け替えるだけで済ますことができます。図 4 を見てください。セル xs1 の後ろにあるセル xs2 を削除する場合、セル xs1 の link をセル xs3 への参照に書き換えればいいのです。セル xs3 はセル xs2 の link から求めることができます。
プログラムをリスト 6 に示します。
リスト 6 : データの削除
public Object remove(int n) {
Cell xs = nth(n - 1);
Cell ys = xs.getLink();
if (ys == null) {
throw new ListIndexOutOfBoundsException("SinglyLinkedList");
}
xs.setLink(ys.getLink());
size--;
return ys.getValue();
}
データを削除する場合も、削除する位置のひとつ手前のセルが必要になります。nth() で n - 1 番目のセルを求めます。セル xs が見つかれば、xs の後ろのセル ys を削除します。ys は xs.getLink() で求めることができます。
ys が null ならば、削除するセルが無いので例外を送出します。xs.setLink() で xs の link を ys の後ろのセル ys.getLink() に書き換えます。最後に size を -1 してから、削除した要素を ys.getValue() で求めて返します。
ところで、連結リストからはずされたセルは head からアクセスすることができなくなります。Java の場合、どの変数からも参照されなくなったオブジェクトはゴミとなり、「ゴミ集め (GC)」[*2] によって回収されて再利用されます。
GC がないプログラミング言語では、不要になったオブジェクトは自動的に回収されません。それを行うようにプログラムする必要があるのです。Java のように GC があるプログラミング言語では、ゴミになったオブジェクトは自動的に回収されるので、プログラマの負担はそれだけ軽くなります。
[*2] 不要になったオブジェクトを自動的に回収する機能を「ガベージコレクション (Garbage Collection)」と呼びます。
●その他の操作メソッド
残りのメソッドは簡単です。次のリストを見てください。
リスト 7 : その他の操作メソッド
// 書き換え
public Object set(int n, Object obj) {
Cell xs = nth(n);
Object old = xs.getValue();
xs.setValue(obj);
return old;
}
// 空にする
public void clear() {
head.setLink(null);
size = 0;
}
// 個数を求める
public int size() { return size; }
// 空リストか
public boolean isEmpty() { return size == 0; }
要素を書き換えるメソッド set() は、nth() で n 番目のセル cp を求め、xs.setValue(obj) で要素を obj に書き換えます。clear() も簡単で、head.setLink(null) でヘッダーセルの link を null に書き換えて size を 0 にするだけです。要素の個数を求める size() は、フィールド変数 size を返すだけです。isEmpty() は size が 0 かチェックするだけです。
●データの変換
このほかに、連結リストを配列に変換するメソッド toArray() と文字列に変換するメソッド toString() を定義すると便利です。リスト 8 を見てください。
リスト 8 : データの変換
// 配列に変換する
public Object[] toArray() {
Object[] a = new Object [size];
Cell xs = head.getLink();
for (int i = 0; i < size; i++) {
a[i] = xs.getValue();
xs = xs.getLink();
}
return a;
}
// 文字列に変換
public String toString() {
String buff = "(";
Cell xs = head.getLink();
while (xs != null) {
buff += xs.getValue().toString();
xs = xs.getLink();
if (xs != null) buff += " ";
}
buff += ")";
return buff;
}
toArray() は簡単です。Object 型の配列 a を用意し、連結リストをたどって要素を配列に格納していくだけです。toString() も簡単で、要素を toString() で文字列に変換し、それを変数 buff に追加していくだけです。演算子 + で文字列を連結すると新しい文字列が生成されるので、連結リストが長くなると非効率になりますが、簡単にプログラムすることができます。
●ボクシングとアンボクシング
ところで、連結リストはオブジェクトを格納するので、数や boolean などの基本データ型 (プリミティブ型ともいう) をそのまま格納することはできません。Java には基本データ型に対応するクラス (プリミティブラッパークラス) があり、それに変換することでデータを連結リストに格納することができます。基本データ型とそれに対応するラッパークラスを表 2 に示します。
| 基本データ型 | ラッパークラス |
|---|---|
| boolean | Boolean |
| char | Character |
| byte | Byte |
| short | Short |
| int | Integer |
| long | Long |
| float | Float |
| double | Double |
基本データ型をラッパークラスに変換することを「ボクシング (boxing)」といい、逆にラッパークラスを基本データ型に変換することを「アンボクシング (unboxing)」といいます。たとえば、int と Integer の変換は次のように行います。
jshell> var n1 = new Integer(10) n1 ==> 10 jshell> var n2 = Integer.valueOf(100) n2 ==> 100 jshell> Integer n3 = 1000 n3 ==> 1000 jshell> int m1 = n1.intValue() m1 ==> 10 jshell> int m2 = n2 m2 ==> 100 jshell> /vars | Integer n1 = 10 | Integer n2 = 100 | Integer n3 = 1000 | int m1 = 10 | int m2 = 100
ボクシングはコンストラクタを使ってインスタンスを生成する、もしくはクラスメソッド valueOf() を使います。アンボクシングはメソッド intValue() を使います。これは int に変換するときに使用するメソッドで、他のデータ型に変換するメソッドもあります。
Java は JDK 5 から自動的にボクシングとアンボクシングを行うようになりました。この機能を「オートボクシング」といいます。Integer n3 = 1000 は 1000 が自動的にラッパークラス Integer に変換されます。int m2 = n2 は Integer クラスのインスタンス n2 が自動的に int に変換されます。
ところで、ラッパークラスは参照型データなので、演算子 == で比較すると、値が等しくても false になる場合があります。次の例を見てください。
jshell> var n1 = new Integer(100) n1 ==> 100 jshell> var n2 = new Integer(100) n2 ==> 100 jshell> n1 == n2 $3 ==> false jshell> n1 == 100 $4 ==> true jshell> 100 == n2 $5 ==> true jshell> n1.equals(n2) $6 ==> true
new で Integer のインスタンスを生成し、変数 n1 と n2 にセットします。どちらも同じ値ですが、別々のインスタンスなので n1 == n2 は false になります。100 と比較すると、自動的にアンボクシングされるので n1 == 100 と 100 == n2 は true になります。また、メソッド equals() を使って n1 と n2 を比較すると true になります。オートボクシングは便利な機能ですが、演算子 == を使うときには十分に注意してください。
●実行例
それでは簡単な実行例を示しましょう。
リスト 9 : 簡単なテスト
public class SList0 {
public static void main(String[] args) {
var xs = new SinglyLinkedList();
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
for (int i = 0; i < 10; i++) {
System.out.println("insert: " + i + ", "+ i);
xs.insert(i, i);
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
}
for (Object n: xs.toArray()) System.out.print(n + " ");
System.out.println();
for (int i = 0; i < 10; i++) {
xs.set(i, (int)xs.get(i) + 10);
System.out.print(xs.get(i) + " ");
}
System.out.println();
for(int i = 0; i < 5; i++) {
System.out.println("remove: " + i);
System.out.println(xs.remove(i));
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
}
System.out.println("clear:");
xs.clear();
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
}
}
$ javac SList0.java $ java SList0 () 0 true insert: 0, 0 (0) 1 false insert: 1, 1 (0 1) 2 false insert: 2, 2 (0 1 2) 3 false insert: 3, 3 (0 1 2 3) 4 false insert: 4, 4 (0 1 2 3 4) 5 false insert: 5, 5 (0 1 2 3 4 5) 6 false insert: 6, 6 (0 1 2 3 4 5 6) 7 false insert: 7, 7 (0 1 2 3 4 5 6 7) 8 false insert: 8, 8 (0 1 2 3 4 5 6 7 8) 9 false insert: 9, 9 (0 1 2 3 4 5 6 7 8 9) 10 false 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 remove: 0 10 (11 12 13 14 15 16 17 18 19) 9 false remove: 1 12 (11 13 14 15 16 17 18 19) 8 false remove: 2 14 (11 13 15 16 17 18 19) 7 false remove: 3 16 (11 13 15 17 18 19) 6 false remove: 4 18 (11 13 15 17 19) 5 false clear: () 0 true
正常に動作していますね。
●問題
- SinglyLinkedList を継承して、格納するデータの個数を制限するクラス FixedList を定義してください
- SinglyLinkedList を使って「スタック (stack)」を作ってください
- Stack(), コンストラクタ
- void push(Object obj), スタックに obj を追加する
- Object pop(), スタックからデータを取り出す
- boolean isEmpty(), スタックが空ならば true を返す
スタックは基本的なデータ構造の一つです。下図を見てください。
図 : スタックの動作例
図はバネがついた容器を表していて、上から品物を出し入れすることができます。初めは空の状態です。ここに品物を乗せると、重さによってバネを圧縮し、品物が容器に格納されます。さらにもうひとつ品物を上に乗せると、さらにバネを圧縮し、その品物も容器に格納することができます。バネが限界まで圧縮されると、もう品物は追加できなくなります。取り出す場合は、上にある品物から行います。ひとつ取り出すと、その分バネが伸びて下にある品物が上に押し出されます。
この容器の動作がスタックの動作になります。スタックにデータを追加する操作をプッシュ (PUSH) といい、スタックからデータを取り出す操作をポップ (POP) といいます。品物をデータに見立てれば、データ A をスタックにプッシュし (2)、次にデータ B をプッシュします (3)。データを取り出す場合、あとから入れたデータ B が先にポップされ (4)、その次にデータ A がポップされてスタックが空になります (5)。
このように、スタックはあとから入れたデータが先に取り出されるので、後入れ先出し (LIFO : Last-In, First-Out) と呼ばれます。
●解答
リスト : 解答例
// 制限付き連結リスト
class FixedList extends SinglyLinkedList {
final private int upperLimit;
// コンストラクタ
FixedList(int n) {
super();
upperLimit = n;
}
// データの挿入
@Override
public void insert(int n, Object obj) {
if (size() < upperLimit) {
super.insert(n, obj);
}
}
// 満杯か？
public boolean isFull() {
return size() == upperLimit;
}
}
// スタック
class Stack {
SinglyLinkedList stack;
// コンストラクタ
Stack() {
stack = new SinglyLinkedList();
}
// データの追加
public void push(Object obj) {
stack.insert(0, obj);
}
// データの取り出し
public Object pop() {
return stack.remove(0);
}
// 空か？
public boolean isEmpty() {
return stack.isEmpty();
}
}
// 簡単なテスト
public class SList0 {
public static void main(String[] args) {
//
// ・・・省略・・・
//
var ys = new FixedList(5);
for (int i = 0; i < 6; i++) {
System.out.println("insert: " + i);
ys.insert(i, i);
System.out.println(ys);
System.out.println(ys.isFull());
}
var zs = new Stack();
for (int i = 0; i < 8; i++) {
System.out.println("push: " + i);
zs.push(i);
}
while (!zs.isEmpty()) {
System.out.println("pop: " + (int)zs.pop());
}
}
}
$ javac SList0.java $ java SList0 ・・・省略・・・ insert: 0 (0) false insert: 1 (0 1) false insert: 2 (0 1 2) false insert: 3 (0 1 2 3) false insert: 4 (0 1 2 3 4) true insert: 5 (0 1 2 3 4) true push: 0 push: 1 push: 2 push: 3 push: 4 push: 5 push: 6 push: 7 pop: 7 pop: 6 pop: 5 pop: 4 pop: 3 pop: 2 pop: 1 pop: 0
●プログラムリスト
//
// SList0.java : 片方向連結リスト
//
// Copyright (C) 2009-2021 Makoto Hiroi
//
// 例外クラス
class ListIndexOutOfBoundsException extends IndexOutOfBoundsException {
public ListIndexOutOfBoundsException() { }
public ListIndexOutOfBoundsException(String msg) { super(msg); }
}
// セル
class Cell {
// フィールド変数
private Object value;
private Cell link;
// コンストラクタ
Cell(Object obj, Cell xs) {
value = obj;
link = xs;
}
// アクセスメソッド
Object getValue() { return value; }
Cell getLink() { return link; }
void setValue(Object obj) { value = obj; }
void setLink(Cell xs) { link = xs; }
}
// 連結リスト
class SinglyLinkedList {
// フィールド変数
private Cell head;
private int size;
// コンストラクタ
SinglyLinkedList() {
head = new Cell(null, null); // ヘッダーセル
size = 0;
}
// n 番目のセルを求める
private Cell nth(int n) {
int i = -1;
Cell xs = head;
while (xs != null) {
if (n == i) return xs;
i++;
xs = xs.getLink();
}
throw new ListIndexOutOfBoundsException("SinglyLinkedList");
}
// 参照
public Object get(int n) {
return nth(n).getValue();
}
// 挿入
public void insert(int n, Object obj) {
Cell xs = nth(n - 1);
Cell ys = new Cell(obj, xs.getLink());
xs.setLink(ys);
size++;
}
// 削除
public Object remove(int n) {
Cell xs = nth(n - 1);
Cell ys = xs.getLink();
if (ys == null) {
throw new ListIndexOutOfBoundsException("SinglyLinkedList");
}
xs.setLink(ys.getLink());
size--;
return ys.getValue();
}
// 書き換え
public Object set(int n, Object obj) {
Cell xs = nth(n);
Object old = xs.getValue();
xs.setValue(obj);
return old;
}
// 空にする
public void clear() {
head.setLink(null);
size = 0;
}
// 個数を求める
public int size() { return size; }
// 空リストか
public boolean isEmpty() { return size == 0; }
// 配列に変換する
public Object[] toArray() {
Object[] a = new Object [size];
Cell xs = head.getLink();
for (int i = 0; i < size; i++) {
a[i] = xs.getValue();
xs = xs.getLink();
}
return a;
}
// 文字列に変換
public String toString() {
String buff = "(";
Cell xs = head.getLink();
while (xs != null) {
buff += xs.getValue().toString();
xs = xs.getLink();
if (xs != null) buff += " ";
}
buff += ")";
return buff;
}
}
// 制限付き連結リスト
class FixedList extends SinglyLinkedList {
final private int upperLimit;
// コンストラクタ
FixedList(int n) {
super();
upperLimit = n;
}
// データの挿入
@Override
public void insert(int n, Object obj) {
if (size() < upperLimit) {
super.insert(n, obj);
}
}
// 満杯か？
public boolean isFull() {
return size() == upperLimit;
}
}
// スタック
class Stack {
SinglyLinkedList stack;
// コンストラクタ
Stack() {
stack = new SinglyLinkedList();
}
// データの追加
public void push(Object obj) {
stack.insert(0, obj);
}
// データの取り出し
public Object pop() {
return stack.remove(0);
}
// 空か？
public boolean isEmpty() {
return stack.isEmpty();
}
}
// 簡単なテスト
public class SList0 {
public static void main(String[] args) {
SinglyLinkedList xs = new SinglyLinkedList();
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
for (int i = 0; i < 10; i++) {
System.out.println("insert: " + i + ", "+ i);
xs.insert(i, i);
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
}
for (Object n: xs.toArray()) System.out.print(n + " ");
System.out.println();
for (int i = 0; i < 10; i++) {
xs.set(i, (int)xs.get(i) + 10);
System.out.print(xs.get(i) + " ");
}
System.out.println();
for(int i = 0; i < 5; i++) {
System.out.println("remove: " + i);
System.out.println(xs.remove(i));
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
}
System.out.println("clear:");
xs.clear();
System.out.println(xs);
System.out.println(xs.size());
System.out.println(xs.isEmpty());
var ys = new FixedList(5);
for (int i = 0; i < 6; i++) {
System.out.println("insert: " + i);
ys.insert(i, i);
System.out.println(ys);
System.out.println(ys.isFull());
}
var zs = new Stack();
for (int i = 0; i < 8; i++) {
System.out.println("push: " + i);
zs.push(i);
}
while (!zs.isEmpty()) {
System.out.println("pop: " + (int)zs.pop());
}
}
}
}
改訂 2016 年 11 月 12 日
改訂二版 2021 年 2 月 14 日