Web連載「数学ガールの秘密ノート」 第323回　アルゴリズム、なかなか大変（前編）

girlnote323-contains-instance.java

// 注意：本文に近付けるため、Javaとしては不自然な書き方になっています
// cf: https://cakes.mu/posts/33738
class List {
    Node head;

    public List(int... values) {
        this.head = new Node(0, null);
        this.head.next = this.head;
        Node p = this.head;
        for (int i = values.length - 1; i >= 0; i--) {
            p = new Node(values[i], p);
        }
        this.head.next = p;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node p = head.next;
        while (p != head) {
            sb.append(p.value);
            p = p.next;
            if (p != head) {
                sb.append(" → ");
            }
        }
        return sb.toString();
    }

    // List 10
    public boolean contains1(int v) {
        Node p = head.next;
        while (p != head) {
            if (p.value == v) {
                return true;
            }
            p = p.next;
        }
        return false;
    }

    // List 11
    public boolean contains2(int v) {
        head.value = v;
        Node p = head.next;
        while (p.value != v) {
            p = p.next;
        }
        return p != head;
    }

    class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        List c = new List(31, 41, 59, 26, 53);
        System.out.println("" + c);
        System.out.println("Does <31, 41, 59, 26, 53> contain 59? => " + c.contains1(59));
        System.out.println("Does <31, 41, 59, 26, 53> contain 99? => " + c.contains1(99));
        System.out.println("Does <31, 41, 59, 26, 53> contain 59? => " + c.contains2(59));
        System.out.println("Does <31, 41, 59, 26, 53> contain 99? => " + c.contains2(99));
    }
}

https://twitter.com/hyuki/status/1393206340202369028