新・アルゴリズムとデータ構造入門Java編11:双方向連結リストに削除機能を追加する

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() {
        for (Node x = dummy.prev; x != dummy; x = x.prev) {
            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;
    }

    Node insertAfter(Node x, int value) {
        Node newNode = new Node(value);
        x.next.prev = newNode;
        newNode.next = x.next;
        newNode.prev = x;
        x.next = newNode;
        return newNode;
    }

    Node insertBefore(Node x, int value) {
        Node newNode = new Node(value);
        x.prev.next = newNode;
        newNode.prev = x.prev;
        newNode.next = x;
        x.prev = newNode;
        return newNode;
    }

    void erase(Node x) {
        // もし x がダミーノードであれば
        // エラーを出力
        // x の次のノードの prev を x の前のノードに更新
        // x の前のノードの next を x の次のノードに更新
    }

}


public class Main {

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

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

        // node2 を削除

        // リストを出力
        // 逆向きに出力
    }
}

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() {
        for (Node x = dummy.prev; x != dummy; x = x.prev) {
            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;
    }

    Node insertAfter(Node x, int value) {
        Node newNode = new Node(value);
        x.next.prev = newNode;
        newNode.next = x.next;
        newNode.prev = x;
        x.next = newNode;
        return newNode;
    }

    Node insertBefore(Node x, int value) {
        Node newNode = new Node(value);
        x.prev.next = newNode;
        newNode.prev = x.prev;
        newNode.next = x;
        x.prev = newNode;
        return newNode;
    }

    void erase(Node x) {
        // もし x がダミーノードであれば
        // エラーを出力
        // x の次のノードの prev を x の前のノードに更新
        // x の前のノードの next を x の次のノードに更新
    }

}


public class Main {

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

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

        // node2 を削除

        // リストを出力
        // 逆向きに出力
    }
}

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() {
		for (Node x = dummy.prev; x != dummy; x = x.prev) {
			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;
	}

	Node insertAfter(Node x, int value) {
		Node newNode = new Node(value);
		x.next.prev = newNode;
		newNode.next = x.next;
		newNode.prev = x;
		x.next = newNode;
		return newNode;
	}

	Node insertBefore(Node x, int value) {
		Node newNode = new Node(value);
		x.prev.next = newNode;
		newNode.prev = x.prev;
		newNode.next = x;
		x.prev = newNode;
		return newNode;
	}

	void erase(Node x) {
		if (x == dummy) {
			throw new RuntimeException("ダミーノードは削除できません");
		}
		x.next.prev = x.prev;
		x.prev.next = x.next;
	}

	Node pushFront(int value) {
		// 最初に挿入・ここにコードを書く
	}

	Node pushBack(int value) {
		// 最後に挿入・ここにコードを書く
	}

	void popFront() {
		// 最初を削除・ここにコードを書く
	}

	void popBack() {
		// 最後を削除・ここにコードを書く
	}
}


public class Main {

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

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

		list.popBack();

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

		list.pushFront(0);

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

		list.popFront();

		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() {
		for (Node x = dummy.prev; x != dummy; x = x.prev) {
			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;
	}

	Node insertAfter(Node x, int value) {
		Node newNode = new Node(value);
		x.next.prev = newNode;
		newNode.next = x.next;
		newNode.prev = x;
		x.next = newNode;
		return newNode;
	}

	Node insertBefore(Node x, int value) {
		Node newNode = new Node(value);
		x.prev.next = newNode;
		newNode.prev = x.prev;
		newNode.next = x;
		x.prev = newNode;
		return newNode;
	}

	void erase(Node x) {
		if (x == dummy) {
			throw new RuntimeException("ダミーノードは削除できません");
		}
		x.next.prev = x.prev;
		x.prev.next = x.next;
	}

	Node pushFront(int value) {
		// 最初に挿入・ここにコードを書く
	}

	Node pushBack(int value) {
		// 最後に挿入・ここにコードを書く
	}

	void popFront() {
		// 最初を削除・ここにコードを書く
	}

	void popBack() {
		// 最後を削除・ここにコードを書く
	}
}


public class Main {

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

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

		list.popBack();

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

		list.pushFront(0);

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

		list.popFront();

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

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です