リスト （ list ） とは、データの列が格納できるデータ構造です。 リストは、いくつかの節点から構成されます。 一つ一つの節点はレコードで表され、レコードの要素はデータ・フィールドとポインタ・フィールドです。 データ・フィールドにはデータが一つ格納され、ポインタ・フィールドには次の節点へのポインタが格納されます。 次の図はリストの節点のイメージです。
ポインタ・フィールドには、どこも指していないという特別なポインタnullも格納できます。 これは、最後の節点を意味します。
ここで、データ 1, 2, 3 のリストを [1, 2, 3] と書くことにします。 リスト [1, 2, 3] のイメージは次の通りです。
リストは配列に似ています。 どちらもデータの列が格納できます。 配列とリストの主な違いは次の通りです。
| 操作 | 配列 | リスト |
|---|---|---|
| 長さの変更 | 不可能 | 可能 |
| 要素の挿入 | 他の要素も操作 | 挿入要素のみ操作 |
| 要素の削除 | 他の要素も操作 | 削除要素のみ操作 |
| 第i要素へのアクセス | 直接可能 | ポインタをi回たどったら可能 |
| 左の要素へのアクセス | 直接可能 | 最初からポインタをたどりなおしたら可能 |
なお、リストを操作しやすくするために、リストの先頭には必ずダミー・データを追加することにします。 したがって、リスト [1, 2, 3] のイメージは次のようになります。
![リスト [1, 2, 3] のイメージ](ListD123.png)
空リスト（データのないリスト）のイメージは次の通りです。
それでは、リストを扱うプログラムを作成します。
Java言語ですので、ポインタは参照、レコードはインスタンス、レコード型はクラスと言い換えます。
nullは
null
のままとし、dummyは定数
DUMMY
= 0 とします。
まず、リストの節点のクラス
ListNode
を次のように定義します。
data
フィールドにデータを格納し、
next
フィールドに次のインスタンスを格納します。
コンストラクタも定義します。
/* 1*/ class ListNode { /* 2*/ int data; /* 3*/ ListNode next; /* 4*/ ListNode (int data, ListNode next) { /* 5*/ this.data = data; /* 6*/ this.next = next; /* 7*/ } /* 8*/ }
以下ではプログラムの例を紹介しますが、できるだけ、配列の場合とリストの場合を比較することにします。
次のプログラムは、配列 {1, 2, 3} を生成し、その要素を出力するものです。 a[0] には、ダミー・データを格納します。
/* 1*/ class ArrayTest { /* 2*/ public static void main (String[] args) { /* 3*/ int DUMMY = 0; /* 4*/ int[] a = new int[4]; /* 5*/ a[0] = DUMMY; /* 6*/ a[1] = 1; /* 7*/ a[2] = 2; /* 8*/ a[3] = 3; /* 9*/ System.out.println(a[1]); /* 10*/ System.out.println(a[2]); /* 11*/ System.out.println(a[3]); /* 12*/ } /* 13*/ }
asiaa1:~/comp3b b08a001$ java ArrayTest 1 2 3 asiaa1:~/comp3b b08a001$
次のプログラムは、リスト [1, 2, 3] を作成し、その要素を出力するものです。
/* 1*/ class ListTest { /* 2*/ public static void main (String[] args) { /* 3*/ int DUMMY = 0; /* 4*/ ListNode list = new ListNode(DUMMY, null); /* 5*/ list.next = new ListNode(1, null); /* 6*/ list.next.next = new ListNode(2, null); /* 7*/ list.next.next.next = new ListNode(3, null); /* 8*/ System.out.println(list.next.data); /* 9*/ System.out.println(list.next.next.data); /* 10*/ System.out.println(list.next.next.next.data); /* 11*/ } /* 12*/ }
asiaa1:~/comp3b b08a001$ java ListTest 1 2 3 asiaa1:~/comp3b b08a001$
リストが生成されるイメージは、次の通りです。
リストは配列とは異なり、要素の挿入や削除が容易だと説明しました。 実際のプログラムを紹介します。
次のプログラムは、配列 {1, 2, 3} の先頭の要素を削除するものです。 長さが一つ短い配列を用意し、要素を一つずつコピーしています。
/* 1*/ class ArrayDelete { /* 2*/ public static void main (String[] args) { /* 3*/ int DUMMY = 0; /* 4*/ int[] a = new int[4]; /* 5*/ int[] b; /* 6*/ a[0] = DUMMY; /* 7*/ a[1] = 1; /* 8*/ a[2] = 2; /* 9*/ a[3] = 3; /* 10*/ b = new int[a.length - 1]; /* 11*/ b[0] = DUMMY; /* 12*/ b[1] = a[2]; /* 13*/ b[2] = a[3]; /* 14*/ System.out.println(b[1]); /* 15*/ System.out.println(b[2]); /* 16*/ } /* 17*/ }
asiaa1:~/comp3b b08a001$ java ArrayDelete 2 3 asiaa1:~/comp3b b08a001$
次のプログラムは、リスト [1, 2, 3] の先頭の要素を削除するものです。 8行目の代入文 list . next = list . next . next だけで削除しています。
/* 1*/ class ListDelete { /* 2*/ public static void main (String[] args) { /* 3*/ int DUMMY = 0; /* 4*/ ListNode list = new ListNode(DUMMY, null); /* 5*/ list.next = new ListNode(1, null); /* 6*/ list.next.next = new ListNode(2, null); /* 7*/ list.next.next.next = new ListNode(3, null); /* 8*/ list.next = list.next.next; /* 9*/ System.out.println(list.next.data); /* 10*/ System.out.println(list.next.next.data); /* 11*/ } /* 12*/ }
asiaa1:~/comp3b b08a001$ java ListDelete 2 3 asiaa1:~/comp3b b08a001$
この手続きのイメージは以下の通りです。
次のプログラムは、配列 {2, 3} の先頭に要素1を挿入するものです。 長さが一つ長い配列を用意し、要素を一つずつコピーしています。
/* 1*/ class ArrayInsert { /* 2*/ public static void main (String[] args) { /* 3*/ int DUMMY = 0; /* 4*/ int[] a = new int[3]; /* 5*/ int[] b; /* 6*/ a[0] = DUMMY; /* 7*/ a[1] = 2; /* 8*/ a[2] = 3; /* 9*/ b = new int[a.length + 1]; /* 10*/ b[0] = DUMMY; /* 11*/ b[1] = 1; /* 12*/ b[2] = a[1]; /* 13*/ b[3] = a[2]; /* 14*/ System.out.println(b[1]); /* 15*/ System.out.println(b[2]); /* 16*/ System.out.println(b[3]); /* 17*/ } /* 18*/ }
asiaa1:~/comp3b b08a001$ java ArrayInsert 1 2 3 asiaa1:~/comp3b b08a001$
次のプログラムは、リスト [2, 3] の先頭に要素1を挿入するものです。 7行目では、新しく節点を生成し、そのポインタ・フィールドに list . next の値を格納してから、 list . next に生成した節点を格納しています。
/* 1*/ class ListInsert { /* 2*/ public static void main (String[] args) { /* 3*/ int DUMMY = 0; /* 4*/ ListNode list = new ListNode(DUMMY, null); /* 5*/ list.next = new ListNode(2, null); /* 6*/ list.next.next = new ListNode(3, null); /* 7*/ list.next = new ListNode(1, list.next); /* 8*/ System.out.println(list.next.data); /* 9*/ System.out.println(list.next.next.data); /* 10*/ System.out.println(list.next.next.next.data); /* 11*/ } /* 12*/ }
asiaa1:~/comp3b b08a001$ java ListInsert 1 2 3 asiaa1:~/comp3b b08a001$
この手続きのイメージは以下の通りです。
配列では、for文などの繰り返しを利用して、長い配列を処理しました。 リストでも、繰り返し文を使って、長い配列を処理します。
次のプログラムは、配列 {1, 2, 3, 4, 5, 6, 7, 8, 9} を作成し、その要素を出力するものです。
/* 1*/ class ArrayLoop { /* 2*/ public static void main (String[] args) { /* 3*/ int i, DUMMY = 0; /* 4*/ int[] a = new int[10]; /* 5*/ a[0] = DUMMY; /* 6*/ for (i = 1; i <= 9; i++) { /* 7*/ a[i] = i; /* 8*/ } /* 9*/ for (i = 1; i < a.length; i++) { /* 10*/ System.out.print(" " + a[i]); /* 11*/ } /* 12*/ System.out.println(); /* 13*/ } /* 14*/ }
asiaa1:~/comp3b b08a001$ java ArrayLoop 1 2 3 4 5 6 7 8 9 asiaa1:~/comp3b b08a001$
次のプログラムは、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] を作成し、その要素を出力するものです。
長いリストですので、生成するときに
list
.
next
.
next
.... と書くわけにはいきません。
そこで、7行目の
for
文の前に、
x
に
list
の値を格納しておき、
for
文の中では、
x
.
next
にリストの節点を格納してから、
x
の値を
x
.
next
に変更します。
リストの要素を出力するときも、同様に代入文
x
=
x
.
next
を繰り返します。
ただし、これは11行目の
for
文の丸括弧に入っています。
この繰り返しを、
x
の値がnullになるまで行います。
/* 1*/ class ListLoop { /* 2*/ public static void main (String[] args) { /* 3*/ int i, DUMMY = 0; /* 4*/ ListNode list = new ListNode(DUMMY, null); /* 5*/ ListNode x; /* 6*/ x = list; /* 7*/ for (i = 1; i <= 9; i++) { /* 8*/ x.next = new ListNode(i, null); /* 9*/ x = x.next; /* 10*/ } /* 11*/ for (x = list.next; x != null; x = x.next) { /* 12*/ System.out.print(" " + x.data); /* 13*/ } /* 14*/ System.out.println(); /* 15*/ } /* 16*/ }
asiaa1:~/comp3b b08a001$ java ListLoop 1 2 3 4 5 6 7 8 9 asiaa1:~/comp3b b08a001$
リストは配列より常に優れているわけではありません。 例えば、要素数を数えたり、最後の要素を取り出すことは、配列の方が簡単です。 実際、配列の要素数は、
a.length - 1
で求められます。 （1 を引くのはダミー・データのためです。） また、最後の要素は、
a[a.length - 1]
で求められます。
次のプログラムは、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] の要素数を数えるものです。 リストを先頭から末尾までたどりながら、要素数を数えています。
/* 1*/ class ListLength { /* 2*/ public static void main (String[] args) { /* 3*/ int i, len, DUMMY = 0; /* 4*/ ListNode list = new ListNode(DUMMY, null); /* 5*/ ListNode x; /* 6*/ x = list; /* 7*/ for (i = 1; i <= 9; i++) { /* 8*/ x.next = new ListNode(i, null); /* 9*/ x = x.next; /* 10*/ } /* 11*/ len = 0; /* 12*/ for (x = list.next; x != null; x = x.next) { /* 13*/ len++; /* 14*/ } /* 15*/ System.out.println(len); /* 16*/ } /* 17*/ }
asiaa1:~/comp3b b08a001$ java ListLength 9 asiaa1:~/comp3b b08a001$
リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] の最後の要素を求めるプログラムを作成してください。 リストを先頭から末尾の直前までたどり、そこのデータを取り出すと、うまく行きます。 プログラムは穴埋めとします。
class ListLast {
public static void main (String[] args) {
int i, DUMMY = 0;
ListNode list = new ListNode(DUMMY, null);
ListNode x;
x = list;
for (i = 1; i <= 9; i++) {
x.next = new ListNode(i, null);
x = x.next;
}
???
System.out.println(x.data);
}
}
asiaa1:~/comp3b b08a001$ java ListLast 9 asiaa1:~/comp3b b08a001$
今日の演習7の答案（Javaプログラム）をメールで提出してください。 差出人は学内のメール・アドレス（b08a001@cis.twcu.ac.jpなど）とし、宛先はkonishi@cis.twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（11月14日）を明記してください。