新・アルゴリズムとデータ構造入門Java編11:双方向連結リストの作成

import java.util.Scanner;

class Node {
    // Node クラスに値を表す変数 value を用意
    // Node クラスに次のノードへの参照を表す変数 next を用意
    // Node クラスに前のノードへの参照を表す変数 prev を用意

    // Node クラスに、値を受け取って初期化する関数を用意
    // 受け取った値を変数 value に代入
}


class List {
    // List クラスに、ダミーノードを表すノード dummy を用意

    // List クラスに、ダミーノード 1 つでリストを初期化する関数を用意
    // ダミーノードを変数 dummy に代入
    // ダミーノードの次のノードをダミーノードに設定
    // ダミーノードの前のノードをダミーノードに設定

    void print() {
        for (Node x = dummy.next; x != dummy; x = x.next) {
            System.out.print(x.value + " ");
        }
        System.out.println();
    }

    Node find(int value) {
        for (Node x = dummy.next; x != dummy; x = x.next) {
            if (x.value == value) {
                return x;
            }
        }
        return dummy;
    }
}


public class Main {

    public static void main(String[] args) {
        // List クラスの変数 list を用意
        // 1, 2, 3 を要素にとるノードを作成

        // 順番に参照をつなぐ

        // 逆方向にも参照をつなぐ

        // リストを出力

        // ダミーノードを出力
        // その前のノードを順番に出力
    }
}

import java.util.Scanner;

class Node {
    // Node クラスに値を表す変数 value を用意
    // Node クラスに次のノードへの参照を表す変数 next を用意
    // Node クラスに前のノードへの参照を表す変数 prev を用意

    // Node クラスに、値を受け取って初期化する関数を用意
    // 受け取った値を変数 value に代入
}


class List {
    // List クラスに、ダミーノードを表すノード dummy を用意

    // List クラスに、ダミーノード 1 つでリストを初期化する関数を用意
    // ダミーノードを変数 dummy に代入
    // ダミーノードの次のノードをダミーノードに設定
    // ダミーノードの前のノードをダミーノードに設定

    void print() {
        for (Node x = dummy.next; x != dummy; x = x.next) {
            System.out.print(x.value + " ");
        }
        System.out.println();
    }

    Node find(int value) {
        for (Node x = dummy.next; x != dummy; x = x.next) {
            if (x.value == value) {
                return x;
            }
        }
        return dummy;
    }
}


public class Main {

    public static void main(String[] args) {
        // List クラスの変数 list を用意
        // 1, 2, 3 を要素にとるノードを作成

        // 順番に参照をつなぐ

        // 逆方向にも参照をつなぐ

        // リストを出力

        // ダミーノードを出力
        // その前のノードを順番に出力
    }
}

import java.util.Scanner;

class Node {
	int value;
	Node next;
	Node prev;

	Node(int value) {
		this.value = value;
	}
}


class List {
	Node dummy;

	List() {
		dummy = new Node(-1);
		dummy.next = dummy;
		dummy.prev = dummy;
	}

	void print() {
		for (Node x = dummy.next; x != dummy; x = x.next) {
			System.out.print(x.value + " ");
		}
		System.out.println();
	}

	void printReverse() {
		// ここにコードを書く
	}

	Node find(int value) {
		for (Node x = dummy.next; x != dummy; x = x.next) {
			if (x.value == value) {
				return x;
			}
		}
		return dummy;
	}
}


public class Main {

	public static void main(String[] args) {
		List list = new List();
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);

		list.dummy.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = list.dummy;

		list.dummy.prev = node3;
		node3.prev = node2;
		node2.prev = node1;
		node1.prev = list.dummy;

		list.print();
		list.printReverse();
	}
}

import java.util.Scanner;

class Node {
	int value;
	Node next;
	Node prev;

	Node(int value) {
		this.value = value;
	}
}


class List {
	Node dummy;

	List() {
		dummy = new Node(-1);
		dummy.next = dummy;
		dummy.prev = dummy;
	}

	void print() {
		for (Node x = dummy.next; x != dummy; x = x.next) {
			System.out.print(x.value + " ");
		}
		System.out.println();
	}

	void printReverse() {
		// ここにコードを書く
	}

	Node find(int value) {
		for (Node x = dummy.next; x != dummy; x = x.next) {
			if (x.value == value) {
				return x;
			}
		}
		return dummy;
	}
}


public class Main {

	public static void main(String[] args) {
		List list = new List();
		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);

		list.dummy.next = node1;
		node1.next = node2;
		node2.next = node3;
		node3.next = list.dummy;

		list.dummy.prev = node3;
		node3.prev = node2;
		node2.prev = node1;
		node1.prev = list.dummy;

		list.print();
		list.printReverse();
	}
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「逆向きの出力用の関数の実装」

動画で作成した双方向連結リストに、以下の条件を満たすように逆向きの出力用の関数を実装してください。

・ダミーノードを除いたすべての要素を後から順に出力する
・各要素の値のあとに半角スペース 1 文字を出力する (最後の値の後にも半角スペース 1 文字を出力する)
・最後に改行を出力する

期待する出力値

1 2 3
3 2 1

Tips

動画へ戻る

次のチャプターへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃05:双方向連結リストの作成

このチャプターでは、双方向連結リストのデータ構造を実装します。

双方向リストのデータ構造

Node クラス：
・値 value をもつ
・次の要素への参照 next をもつ
・前の要素への参照 prev をもつ

List クラス：
・始端、終端を表すノード dummy をもつ
・dummy <-> 最初の要素 <-> ... <-> 最後の要素 <-> dummy になるようにする
・初期化時は、dummy の next, prev が dummy を指すようにする

プログラミング学習 > 新・アルゴリズムとデータ構造入門 Java編 > 新・アルゴリズムとデータ構造入門Java編11: 連結リスト > 双方向連結リストの作成

ログインすると採点できます

コードの実行

有料会員になるとエンジニアに質問ができます

出力タイプ：