コンピュータIIIB(Javaアルゴリズム)第6回
h2 リスト toc-lists
h3 リストとは toc-what-is-a-list
index リスト list りすと
とは、ポインタによってデータの列が表されるデータ構造です。
リストはいくつかのレコードから構成されます。
このレコードのデータ型は、
データ・フィールドとポインタ・フィールドの組です。
データ・フィールドには一つのデータが格納され、
ポインタ・フィールドには次のレコードへのポインタが格納されます。
次の図はレコードのイメージです。
+-----+-----+
| | |
|data | *--+---->
+-----+-----+
ポインタ・フィールドには、
どこも指していないという特別なポインタ null も格納できます。
これは、最後のレコードを意味します。
ここで、データ 1, 2, 3 のリストを [1, 2, 3] と書くことにします。
リスト [1, 2, 3] のイメージは次の通りです。
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
| 1 | *--+---->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+
リストは配列に似ています。
どちらもデータの列が格納できるデータ構造です。
リストと配列の主な違いは次の通りです。
・配列は一度生成しますと長さは変えられませんが、
リストは長さを変えられます。
・データの列の中に要素を挿入する場合、
配列では他の要素も格納しなおす必要がありますが、
リストではその必要はありません。
・データの列の中から要素を削除する場合、
配列では他の要素も格納しなおす必要がありますが、
リストではその必要はありません。
・配列では i 番目の要素にすぐにアクセスできますが、
リストではポインタを i 回たどる必要があります。
・配列では一つ左の要素にすぐにアクセスできますが、
リストでは最初からポインタをたどる必要があります。
なお、リストを操作しやすくするために、
リストの先頭には必ずダミー・データを追加することにします。
すると、リスト [1, 2, 3] のイメージは次のようになります。
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | | | | |
|dummy| *--+---->| 1 | *--+---->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
空リスト (データのないリスト) のイメージは次の通りです。
+-----+-----+
| | |
|dummy|null |
+-----+-----+
h3 リストの例 toc-list-examples
それでは、リストを扱うプログラムを作成します。
Java言語ですので、ポインタは参照、レコードはインスタンス、
レコード型はクラスと言い換えます。
null は null のままとし、dummy は定数 DUMMY = 0 とします。
まず、クラスは次の通りとします。
first フィールドにデータを格納し、
rest フィールドに次のインスタンスを格納します。
コンストラクタも定義します。
class IntList {
int first;
IntList rest;
IntList (int first, IntList rest) {
this.first = first;
this.rest = rest;
}
}
最初の例は、リスト [1, 2, 3] を作成し、その要素を出力するものです。
class ListTest {
public static void main (String[] args) {
int DUMMY = 0;
IntList lst;
lst = new IntList(DUMMY, null);
lst.rest = new IntList(1, null);
lst.rest.rest = new IntList(2, null);
lst.rest.rest.rest = new IntList(3, null);
System.out.println(lst.rest.first);
System.out.println(lst.rest.rest.first);
System.out.println(lst.rest.rest.rest.first);
}
}
リストが作られるイメージは、次の通りです。
+-----+-----+
| | |
|dummy|null |
+-----+-----+
+-----+-----+ +-----+-----+
| | | | | |
|dummy| *--+---->| 1 |null |
+-----+-----+ +-----+-----+
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+---->| 1 | *--+---->| 2 |null |
+-----+-----+ +-----+-----+ +-----+-----+
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | | | | |
|dummy| *--+---->| 1 | *--+---->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
b04a001@AsiaA1:~/comp3b% java ListTest
1
2
3
b04a001@AsiaA1:~/comp3b%
次の例は、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] を作成し、
その要素を出力するものです。
lst.rest.rest.... と書くわけにはいきませんので、
代入文 lst = lst.rest; を繰り返し実行します。
また、リストの先頭に戻る必要がありますので、
この代入文を実行する前に、lst の値を head に格納しておきます。
class ListLoop {
public static void main (String[] args) {
int i, DUMMY = 0;
IntList lst = new IntList(DUMMY, null);
IntList head = lst;
for (i = 1; i <= 9; i++) {
lst.rest = new IntList(i, null);
lst = lst.rest;
}
lst = head.rest;
while (lst != null) {
System.out.print(" " + lst.first);
lst = lst.rest;
}
System.out.println();
}
}
b04a001@AsiaA1:~/comp3b% java ListLoop
1 2 3 4 5 6 7 8 9
b04a001@AsiaA1:~/comp3b%
h3 リストの操作 toc-list-operations
リストは配列とは異なり、要素の挿入や削除が容易だと説明しました。
実際のプログラムを紹介します。
次のプログラムは、リスト [1, 2, 3] の先頭の要素を削除するものです。
代入文 lst.rest = lst.rest.rest; を実行するだけで削除しています。
class ListDelete {
public static void main (String[] args) {
int DUMMY = 0;
IntList lst;
lst = new IntList(DUMMY, null);
lst.rest = new IntList(1, null);
lst.rest.rest = new IntList(2, null);
lst.rest.rest.rest = new IntList(3, null);
lst.rest = lst.rest.rest;
System.out.println(lst.rest.first);
System.out.println(lst.rest.rest.first);
}
}
この手続きのイメージは以下の通りです。
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | | | | |
|dummy| *--+---->| 1 | *--+---->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
+-----------------+
| |
+-----+-----+ | +-----+-----+ | +-----+-----+ +-----+-----+
| | | | | | | +->| | | | | |
|dummy| *--+--+ | 1 | *--+---->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
b04a001@AsiaA1:~/comp3b% java ListDelete
2
3
b04a001@AsiaA1:~/comp3b%
次のプログラムは、リスト [2, 3] の先頭に要素 1 を挿入するものです。
直接 lst.rest に new IntList(1, null) を格納しますと、
残りのリストへの参照を失いますので、その前に temp に格納しておきます。
class ListInsert {
public static void main (String[] args) {
int DUMMY = 0;
IntList lst, temp;
lst = new IntList(DUMMY, null);
lst.rest = new IntList(2, null);
lst.rest.rest = new IntList(3, null);
temp = lst.rest;
lst.rest = new IntList(1, null);
lst.rest.rest = temp;
System.out.println(lst.rest.first);
System.out.println(lst.rest.rest.first);
System.out.println(lst.rest.rest.rest.first);
}
}
この手続きのイメージは以下の通りです。
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+---------------------->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+
+-----+-----+
| | |
| 1 |null |
+-----+-----+
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+--+ +->| 2 | *--+---->| 3 |null |
+-----+-----+ | | +-----+-----+ +-----+-----+
| +-----+-----+ |
| | | | |
+->| 1 | *--+--+
+-----+-----+
b04a001@AsiaA1:~/comp3b% java ListInsert
1
2
3
b04a001@AsiaA1:~/comp3b%
h2 演習 6 toc-exercises
2 つのリストを連接するプログラムを作成してください。
ここで、リスト lst1 と lst2 を連接するとは、
lst1 の要素に続けて lst2 の要素を並べたリストを作成することです。
例えば、[1, 2, 3] と [4, 5] を連接しますと、[1, 2, 3, 4, 5] となります。
リストのイメージでは、リスト
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | | | | |
|dummy| *--+---->| 1 | *--+---->| 2 | *--+---->| 3 |null |
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
と、リスト
+-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | |
|dummy| *--+---->| 4 | *--+---->| 5 |null |
+-----+-----+ +-----+-----+ +-----+-----+
を、リスト
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+
| | | | | | | | | | | |
|dummy| *--+---->| 1 | *--+---->| 2 | *--+---->| 3 | *--+--+
+-----+-----+ +-----+-----+ +-----+-----+ +-----+-----+ |
|
+-----------------------------------------------------+
|
+-----+-----+ | +-----+-----+ +-----+-----+
| | | +->| | | | | |
|dummy| *--+---->| 4 | *--+---->| 5 |null |
+-----+-----+ +-----+-----+ +-----+-----+
とします。
クラスは次の通りです。
class IntList {
int first;
IntList rest;
IntList (int first, IntList rest) {
this.first = first;
this.rest = rest;
}
}
プログラムは穴埋めとします。
次のプログラムのメソッド append を完成させてください。
メソッドの内容は、リスト lst1 の末尾を探し、
そこにリスト lst2 のダミー・データを除いた部分を格納することです。
class ListAppend {
public static void main (String[] args) {
int DUMMY = 0;
IntList lst1, lst2, lst;
lst1 = new IntList(DUMMY, null);
lst1.rest = new IntList(1, null);
lst1.rest.rest = new IntList(2, null);
lst1.rest.rest.rest = new IntList(3, null);
print(lst1);
lst2 = new IntList(DUMMY, null);
lst2.rest = new IntList(4, null);
lst2.rest.rest = new IntList(5, null);
print(lst2);
lst = append(lst1, lst2);
print(lst);
}
static void print (IntList lst) {
for (lst = lst.rest; lst != null; lst = lst.rest) {
System.out.print(" " + lst.first);
}
System.out.println();
}
static IntList append (IntList lst1, IntList lst2) {
???
}
}
b04a001@AsiaA1:~/comp3b% java ListAppend
1 2 3
4 5
1 2 3 4 5
b04a001@AsiaA1:~/comp3b%
2004年10月29日更新
konishi@twcu.ac.jp
Copyright (C) 2004 Zenjiro Konishi.
All rights reserved.