[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIIB(Javaアルゴリズム)第5回

目次
5.1 リスト(1)
5.1.1 リストとは
5.1.2 リストの例
5.1.3 リストの操作
5.2 演習5
5.3 レポート課題
5.4 参考文献
索引
リスト  

5.1 リスト(1)

5.1.1 リストとは

リストlist ) とは、データの列が格納できるデータ構造です。 リストは、いくつかの節点から構成されます。 一つ一つの節点はレコードで表され、レコードの要素はデータ・フィールドとポインタ・フィールドです。 データ・フィールドにはデータが一つ格納され、ポインタ・フィールドには次の節点へのポインタが格納されます。 次の図はリストの節点のイメージです。

An image of a list node
図 5.1  リストの節点のイメージ

ポインタ・フィールドには、どこも指していないという特別なポインタnullも格納できます。 これは、最後の節点を意味します。

ここで、データ 1, 2, 3 のリストを [1, 2, 3] と書くことにします。 リスト [1, 2, 3] のイメージは次の通りです。

An image of a list
図 5.2  リストのイメージ

リストは配列に似ています。 どちらもデータの列が格納できます。 配列とリストの主な違いは次の通りです。

表 5.1  配列とリストの違い
操作 配列 リスト
長さの変更 不可能 可能
要素の挿入 他の要素も操作 挿入要素のみ操作
要素の削除 他の要素も操作 削除要素のみ操作
i要素へのアクセス 直接可能 ポインタをi回たどったら可能
左の要素へのアクセス 直接可能 最初からポインタをたどりなおしたら可能

なお、リストを操作しやすくするために、リストの先頭には必ずダミー・データを追加することにします。 したがって、リスト [1, 2, 3] のイメージは次のようになります。

An image of a list [1, 2, 3]
図 5.3  リスト [1, 2, 3] のイメージ

空リスト(データのないリスト)のイメージは次の通りです。

An image of an empty list
図 5.4  空リストのイメージ

5.1.2 リストの例

それでは、リストを扱うプログラムを作成します。 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%

リストが生成されるイメージは、次の通りです。

An image of an empty list
An image of a list [1]
An image of a list [1, 2]
An image of a list [1, 2, 3]
図 5.5  リスト生成のイメージ

次の例は、リスト [1, 2, 3, 4, 5, 6, 7, 8, 9] を作成し、その要素を出力するものです。

長いリストですので、生成するときに list . next . next .... と書くわけにはいきません。 そこで、あらかじめ xlist の値を格納しておき、 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%

5.1.3 リストの操作

リストは配列とは異なり、要素の挿入や削除が容易だと説明しました。 実際のプログラムを紹介します。

次のプログラムは、リスト [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%

この手続きのイメージは以下の通りです。

An image of list deletion
図 5.6  リスト削除のイメージ

次のプログラムは、リスト [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%

この手続きのイメージは以下の通りです。

An image of list insertion
図 5.7  リスト挿入のイメージ

5.2 演習5

2つのリストを連接するプログラムを作成してください。

ここで、リスト list1list2 を連接するとは、 list1 の要素に続けて list2 の要素を並べたリストを作成することです。 例えば、[1, 2, 3] と [4, 5] を連接しますと、[1, 2, 3, 4, 5] となります。 リストのイメージでは、リスト

An image of a list [1, 2, 3]

と、リスト

An image of a list [4, 5]

を、リスト

An image of list append

とします。

クラスの定義は次の通りです。

/*  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.3 レポート課題

今日の演習5の答案(Javaプログラム)をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(10月28日)を明記してください。


5.4 参考文献


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2005年10月30日更新
小西 善二郎 <konishi@twcu.ac.jp>
Copyright (C) 2005 Zenjiro Konishi. All rights reserved.