クラスライブラリ応用 リスト (演習)

例題1: リストの1つのノードを表すクラス

リスト内の一つ一つのデータはノード (node) または要素 (element) と呼ばれ、 ノードを実現するクラスの内容は以下のとおりである。 なお、簡単化のため、この例ではリストの中に入れるデータは文字列としている。 element はノードに入れる情報本体である。 next は同じ Node クラスのオブジェクトであり、 あるノードから見た「次のノードへの参照 (在りか) 」を示す変数である。

さらに、ノードの情報を初期化するコンストラクタ、 ノードの情報を登録／参照するメソッドを用意し、 次のようなクラスで表すことができる。 (ファイル名 Node.java) 

public class Node {
    private String element;
    private Node next;

    /** コンストラクタ */
    public Node() { }
    public Node(String element, Node next) {
	this.element = element;
	this.next = next;
    }

    /** 次のノードへの参照を登録する */
    public void setNext(Node next) {
	this.next = next;
    }

    /** 次のノードへの参照を返す */
    public Node getNext() {
	return next;
    }

    /** ノードの中身の情報を登録する */
    public void setElement(String element) {
	this.element = element;
    }

    /** ノードの中身の情報を返す */
    public String getElement() {
	return element;
    }
}

例題2: リストにノードを追加する

上で定義したクラス Node を使い簡単なリストを作ることを考える。 リストは次のように宣言し、最初のノードを加えることができる。 

Node head = null;                     // リストの先頭を保持する変数を宣言、最初は空
head = new Node("Copernicus", null);  // 先頭にCopernicusを追加

次に2番目、3番目、4番目の要素を末尾に加えるには次のように書くことができる。 

// リストの末尾に 2番目の要素 Newton を追加
head.setNext(new Node("Newton", null));

// リストの末尾に 3番目の要素 Heisenberg を追加
Node second = head.getNext();
second.setNext(new Node("Heisenberg", null));

// リストの末尾に 4番目の要素 Einstein を追加
Node third = second.getNext();
third.setNext(new Node("Einstein", null));

以上の処理を実行するとリストには 

[head] → Copernicus → Newton → Heisenberg → Einstein → (null)

という順にデータが並んでいることになる。

例題3: リストの中身を順番に調べる

リストを管理するための変数は、先頭を表す head だけである。 先頭の要素さえ分かっていれば、参照をたどることによってすべてのノードに到達できる。 リストのノードを順番にアクセスする方法で代表的なのは、 次のようにリストの先頭から順に調べていく方法である。 

Node p = head;
while (p != null) {
    リストのノード p に関する処理;
    p = p.getNext();
}

次の例は、リストの中身を順番に表示する処理の例である。 

// リスト全体を表示
Node p = head;
while(p != null) {
    System.out.println(p.getElement());
    p = p.getNext();
}

例題4: リストからノードの削除

データが並んだリストから、ノードを削除する方法を考える。 削除対象のノードによって、以下の2とおりに処理を分けて考えると良い。

先頭ノードの削除

以下のノードが存在するリストがあるとする。 

[head]  → Copernicus → Newton → Heisenberg → Einstein → (null)

先頭のノード Copernics を削除することを考える。 (教科書 p.290 の図9-13参照) プログラムは以下のとおりである。head はリストの先頭を指しているとする。 

if (head != null)
    head = head.getNext();

先頭以外のノードの削除

先頭以外のノードの削除を考える。例えば Heisenberg を削除するとする。 (教科書 p.293 の図9-15参照)

まず、削除したい一つ前のノードを探す。この例では Newton である。 「一つ前」というのは不自然な設定であるが、 能率良く処理を行うためにはやむを得ない。 リストは、前に進むのは容易であるが、後ろに戻るのは困難であるからである。 削除したいノードを指定するようにすると、 一つ前のノードを求めるのに時間がかかる。 (この不便を解消するには双方向リストを用いる) 

(あらかじめ、削除対象の Heisenberg の一つ前 (Newton) を探し、p に代入しておく)

if (p != null) {
    Node target = p.getNext();  // target: 削除対象のノード
    Node q = target.getNext();  // q: 削除対象の「次」のノード
    p.setNext(q);
}

=================
各変数が指すノード:
[head]  → Copernicus → Newton → Heisenberg → Einstein → (null)
                          [p]      [target]      [q]
=================

例題5: プログラム全体

上で取り上げた、リストへのデータの追加、削除 リスト全体の表示を含めたプログラム全体を示す。 各自実行して動作を確認すること。

なお、クラス Node は、例題1のものを使う。 

public class LinkedListSample {
    public static void main(String[] args) {
	Node head = null;

	// 最初の要素 Copernicus の追加
	head = new Node("Copernicus", null);

	// リストの末尾に 2番目の要素 Newton を追加
	head.setNext(new Node("Newton", null));

	// リストの末尾に 3番目の要素 Heisenberg を追加
	Node second = head.getNext();
	second.setNext(new Node("Heisenberg", null));

	// リストの末尾に 4番目の要素 Einstein を追加
	Node third = second.getNext();
	third.setNext(new Node("Einstein", null));

        // リスト先頭の要素 (Copernics) を削除
        if (head != null)
            head = head.getNext();

        Node p;

        // リストの2番めの要素 (Heisenberg) を削除
        p = head; // 削除対象の1つ前 (Newton) のノードをpと置く
        if (p != null) {
            Node target = p.getNext();  // target: 削除対象のノード
            Node q = target.getNext();  // q: 削除対象の「次」のノード
            p.setNext(q);
        }

	// リストの内容を表示
        // この時点でのリストは Newton -> Einstein
	p = head;
	while(p != null) {
	    System.out.print(p.getElement());
	    p = p.getNext();
	}
	System.out.println();
    }
}

本日の課題

提出先: /home/submit/JavaLib/[出題日]/[学籍番号]

[注意] 本課題では、1つクラスを1つのファイルとして作成することを想定している。 ファイル名は、「public宣言を行ったクラスの名前.java」 である。 ファイルが別々であっても、同じディレクトリにあるpublic宣言されたクラスは、 相互に利用することができる。 (詳しく知りたい人は、「パッケージ」について調べると良い)

課題 (11/15 20:30まで)

リスト内のデータとリストのさまざまな機能 (データの追加、リスト全体の表示) を 1つのクラスとして設計し実装しなさい。

これまで利用してきた、Javaのクラスライブラリの LinkedList の機能縮小版を自分で作ると考えれば良い。 良いアルゴリズムや良いプログラムを考えるためには、 ソフトウェアの基本的なメカニズムは理解してもらいたい。 この勉強には基本的なデータ構造を自分で作成してみることが一番である。

クラス名 MyLinkedList とし、次のような機能を備えるようにする。

コンストラクタ

MyLinkedList()
中身が空のリストを生成する。

メソッド

addLast(String elem)
リストの末尾に文字列 elem を保持するノードを追加する。 リストに1つもノードが無い場合と、 リストにすでに1つ以上ノードがある場合とを分けて考えると良い。
remove(String elem)
リストから文字列 elem を有するノードを削除する。 削除すべきデータが見つからなかった場合や、リストが空であった場合には エラーメッセージを出力する。 各ノードが有するデータの重複はないものとする。 削除対象のノードがリストの先頭か、2番目以降かを分けて考えると良い。
print()
リストの内容を表示する

addLast, remove の2つのメソッドを作成しなさい。

作成したプログラムが正しく動作するかどうか、必要かつ十分なテストを行うこと。 少なくとも、次のような main メソッドで動作を確認すること。 (提出ファイル名: MyLinkedList.java) 

public class MyLinkedListMain {
    public static void main(String[] args) {
	MyLinkedList list = new MyLinkedList();

	list.addLast("Copernicus");
	list.addLast("Newton");
	list.addLast("Heisenberg");
	list.addLast("Einstein");

        // この時点でのリスト: Copernics -> Newton -> Heisenberg -> Einstein
	list.print();

        // Copernics と Einstein を削除
        list.remove("Copernicus");
	list.remove("Einstein");

	System.out.println("=========[削除後]=========");
        // この時点でのリスト: Newton -> Heisenberg
	list.print();
    }
}

クラス MyLinkedList の大枠は次のようになる。 

public class MyLinkedList {
    private Node head;

    public MyLinkedList() {
	head = null;
    }

    public void addLast(String elem) {
        // ここを考える
    }

    public void remove(String elem) {
        // ここを考える
    }

    public void print() {
        Node p = head;
        while (p != null) {
            System.out.print(p.getElement() + " ");
            p = p.getNext();
        }
        System.out.println();
    }
}

[参考]

ある文字列 string1 が、別の文字列 string2 の内容と等しいかどうかを判定するには、 equals を使う。例を以下に示す。 

if (string1.equals(string2)) {
    string1 と string2 が等しいときの処理
}
TOP > クラスライブラリ応用
東京電機大学 情報メディア学科