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

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

目次 索引
6.1 リスト
6.1.1 リストとは
6.1.2 リストの構成
6.2 リストの操作
6.2.1 要素の探索
6.2.2 要素の挿入
6.2.3 要素の削除
6.2.4 リストのコピー
6.3 リストの使用例
6.4 演習6
6.5 レポート課題

6.1 リスト

6.1.1 リストとは

6.1.2 リストの構成


6.2 リストの操作

6.2.1 要素の探索

6.2.2 要素の挿入

6.2.3 要素の削除

6.2.4 リストのコピー


6.3 リストの使用例


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%

6.4 演習6


6.5 レポート課題


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

2004年10月29日更新
konishi@twcu.ac.jp
Copyright (C) 2004 Zenjiro Konishi. All rights reserved.