リスト ( list ) とは、データの列が格納できるデータ構造です。 リストは、いくつかの節点から構成されます。 一つ一つの節点はレコードで表され、レコードの要素はデータ・フィールドとポインタ・フィールドです。 データ・フィールドにはデータが一つ格納され、ポインタ・フィールドには次の節点へのポインタが格納されます。 次の図はリストの節点のイメージです。
ポインタ・フィールドには、どこも指していないという特別なポインタnullも格納できます。 これは、最後の節点を意味します。
ここで、データ 1, 2, 3 のリストを [1, 2, 3] と書くことにします。 リスト [1, 2, 3] のイメージは次の通りです。
リストは配列に似ています。 どちらもデータの列が格納できます。 配列とリストの主な違いは次の通りです。
操作 | 配列 | リスト |
---|---|---|
長さの変更 | 不可能 | 可能 |
要素の挿入 | 他の要素も操作 | 挿入要素のみ操作 |
要素の削除 | 他の要素も操作 | 削除要素のみ操作 |
第i要素へのアクセス | 直接可能 | ポインタをi回たどったら可能 |
左の要素へのアクセス | 直接可能 | 最初からポインタをたどりなおしたら可能 |
なお、リストを操作しやすくするために、リストの先頭には必ずダミー・データを追加することにします。 したがって、リスト [1, 2, 3] のイメージは次のようになります。
空リスト(データのないリスト)のイメージは次の通りです。
それでは、リストを扱うプログラムを作成します。
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] を作成し、その要素を出力するものです。
/* 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*/ }
b04a001@AsiaA1:~/comp3b% java ListTest 1 2 3 b04a001@AsiaA1:~/comp3b%
リストが生成されるイメージは、次の通りです。
次の例は、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] を作成し、その要素を出力するものです。
長いリストですので、生成するときに list . next . next .... と書くわけにはいきません。 そこで、あらかじめ x に list の値を格納しておき、 x . next にリストの節点を格納してから x の値を x . next に変更することを繰り返します。
リストの要素を出力するときも、同様に代入文
x
=
x
.
next
;を繰り返します。
ただし、この代入文は
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*/ x = list; /* 12*/ for (x = x.next; x != null; x = x.next) { /* 13*/ System.out.print(" " + x.data); /* 14*/ } /* 15*/ System.out.println(); /* 16*/ } /* 17*/ }
b04a001@AsiaA1:~/comp3b% java ListLoop 1 2 3 4 5 6 7 8 9 b04a001@AsiaA1:~/comp3b%
リストは配列とは異なり、要素の挿入や削除が容易だと説明しました。 実際のプログラムを紹介します。
次のプログラムは、リスト [1, 2, 3] の先頭の要素を削除するものです。 代入文 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*/ }
b04a001@AsiaA1:~/comp3b% java ListDelete 2 3 b04a001@AsiaA1:~/comp3b%
この手続きのイメージは以下の通りです。
次のプログラムは、リスト [2, 3] の先頭に要素1を挿入するものです。 新しく節点を生成し、そのポインタ・フィールドに 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*/ }
b04a001@AsiaA1:~/comp3b% java ListInsert 1 2 3 b04a001@AsiaA1:~/comp3b%
この手続きのイメージは以下の通りです。
2つのリストを連接するプログラムを作成してください。
ここで、リスト list1 と list2 を連接するとは、 list1 の要素に続けて list2 の要素を並べたリストを作成することです。 例えば、[1, 2, 3] と [4, 5] を連接しますと、[1, 2, 3, 4, 5] となります。 リストのイメージでは、リスト
と、リスト
を、リスト
とします。
クラスの定義は次の通りです。
/* 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*/ }
プログラムは穴埋めとします。 以下の???の部分に適切な内容を書き込んで、プログラムを完成させてください。 書き込む内容は、リスト list1 の末尾を探し、そこにリスト list2 のダミー・データを除いた部分を格納することです。 リストの末尾は、 list1 . next . next .... のようにも表せますが、これはリストの長さが分かっていないとできません。 リストの長さによらない、一般性のあるプログラムにしてください。
class ListAppend { public static void main (String[] args) { int DUMMY = 0; ListNode list1, list2, x; list1 = new ListNode(DUMMY, null); list1.next = new ListNode(1, null); list1.next.next = new ListNode(2, null); list1.next.next.next = new ListNode(3, null); x = list1; for (x = x.next; x != null; x = x.next) { System.out.print(" " + x.data); } System.out.println(); list2 = new ListNode(DUMMY, null); list2.next = new ListNode(4, null); list2.next.next = new ListNode(5, null); x = list2; for (x = x.next; x != null; x = x.next) { System.out.print(" " + x.data); } System.out.println(); ??? x = list1; for (x = x.next; x != null; x = x.next) { System.out.print(" " + x.data); } System.out.println(); } }
b04a001@AsiaA1:~/comp3b% java ListAppend 1 2 3 4 5 1 2 3 4 5 b04a001@AsiaA1:~/comp3b%
今日の演習5の答案(Javaプログラム)をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(10月28日)を明記してください。