// 第 9 周 – 单链表
// 运行：java SinglyLinkedList.java
public class SinglyLinkedList {

    // 链表结点：值 + 指向下一个结点的指针（引用）
    static class Node {
        int value;
        Node next;

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

    Node head = null; // 空链表：head 为 null(Head ← Nil)

    // 遍历（处理）– O(n)
    //   P ← Head ; While P ≠ Nil : Process(Elem[P].Value) ; P ← Elem[P].Next
    void print() {
        System.out.print("[");
        for (Node p = head; p != null; p = p.next) System.out.print(p.value + (p.next != null ? " -> " : ""));
        System.out.println("]");
    }

    int size() {
        int c = 0;
        for (Node p = head; p != null; p = p.next) c++;
        return c;
    }

    // 查找 – O(n)。返回第一个值为 x 的结点，找不到时返回 null。
    Node find(int x) {
        Node p = head;
        while (p != null && p.value != x) p = p.next;
        return p;
    }

    // 在表头插入 – O(1)
    void insertFirst(int x) {
        head = new Node(x, head); // 新结点指向原来的表头；表头变成新结点
    }

    // 删除表头 – O(1)。返回被删除的值。
    int removeFirst() {
        if (head == null) throw new IllegalStateException("empty list");
        int x = head.value;
        head = head.next; // 原来的第一个结点由垃圾回收器（GC）释放
        return x;
    }

    // 在结点 q 之后插入 – O(1)
    void insertAfter(Node q, int x) {
        q.next = new Node(x, q.next); // 1. 新结点指向 q 原来的后继；2. q 指向新结点
    }

    // 删除结点 q 之后的结点 – O(1)
    void removeAfter(Node q) {
        if (q.next == null) throw new IllegalStateException("there is no element after q");
        q.next = q.next.next;
    }

    // 在表尾插入 – O(n)，因为必须到达最后一个结点
    void insertLast(int x) {
        Node n = new Node(x, null);
        if (head == null) {
            head = n;
            return;
        }
        Node p = head;
        while (p.next != null) p = p.next;
        p.next = n;
    }

    // 删除表尾 – O(n)：必须找到倒数第二个结点
    int removeLast() {
        if (head == null) throw new IllegalStateException("empty list");
        if (head.next == null) {
            int x = head.value;
            head = null;
            return x;
        }
        Node p = head;
        while (p.next.next != null) p = p.next;
        int x = p.next.value;
        p.next = null;
        return x;
    }

    // 删除具有给定值的结点 – O(n)：查找时必须记住前一个结点
    boolean remove(int x) {
        Node prev = null, p = head;
        while (p != null && p.value != x) {
            prev = p;
            p = p.next;
        }
        if (p == null) return false;          // 没有这个元素
        if (prev == null) head = p.next;      // 删除第一个结点
        else prev.next = p.next;
        return true;
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.print();
        list.insertFirst(31);
        list.insertFirst(7);
        list.insertFirst(12);
        System.out.print("3 × insertFirst:     ");
        list.print();

        list.insertLast(5);
        System.out.print("insertLast(5):       ");
        list.print();

        Node q = list.find(7);
        list.insertAfter(q, 99);
        System.out.print("insertAfter(7, 99):  ");
        list.print();

        list.removeAfter(q);
        System.out.print("removeAfter(7):      ");
        list.print();

        System.out.println("removeFirst() = " + list.removeFirst() + ", removeLast() = " + list.removeLast());
        list.print();
        System.out.println("find(31) = " + (list.find(31) != null) + ", find(100) = " + (list.find(100) != null) + ", size = " + list.size());
        list.remove(7);
        System.out.print("remove(7):           ");
        list.print();
    }
}