// 第 10 周 – 带哨兵的链表：Head 指向第一个结点，End 指向末尾的哨兵（空）结点。
// 空链表：Head = End。多亏了哨兵，不需要考虑特殊情况。
// 运行：java SentinelList.java
public class SentinelList {

    static class Node {
        int value;
        Node next;
    }

    Node head, end;

    // 创建：只有一个哨兵结点；Head 和 End 都指向它
    SentinelList() {
        end = new Node();
        head = end;
    }

    boolean isEmpty() { return head == end; }

    // 处理：从 Head 到哨兵（而不是到 null!）
    void print() {
        System.out.print("[");
        for (Node p = head; p != end; p = p.next) System.out.print(p.value + (p.next != end ? " " : ""));
        System.out.println("]");
    }

    // 哨兵查找：把 x 写入哨兵，这样循环只有一个条件
    //   Elem[End].Value ← x ; P ← Head
    //   While Elem[P].Value ≠ x : P ← Elem[P].Next
    //   If P = End then 未找到
    Node search(int x) {
        end.value = x;
        Node p = head;
        while (p.value != x) p = p.next;
        return p == end ? null : p;
    }

    // 在 p 所指结点之前插入 – O(1)，而且是在单链表中！
    // 技巧：把 p 的内容复制到新结点（q）中，把 q 接在 p 之后，p 存放新数据。
    // 如果 p 是哨兵，q 就成为新的哨兵（我们在表尾插入了）。
    void insertBefore(Node p, int x) {
        Node q = new Node();
        q.value = p.value;
        q.next = p.next;
        p.value = x;
        p.next = q;
        if (p == end) end = q;
    }

    // 在表尾插入：插在哨兵之前 – O(1)
    void insertLast(int x) { insertBefore(end, x); }

    // 在表头插入：插在第一个结点之前（空链表时插在哨兵之前）– O(1)
    void insertFirst(int x) { insertBefore(head, x); }

    // 删除 p 所指的结点 – O(1)
    // 技巧：把后继结点（q）的内容复制到 p，然后删除 q。
    // 如果 q 是哨兵，p 就成为新的哨兵。
    void delete(Node p) {
        if (p == end) throw new IllegalArgumentException("the sentinel cannot be deleted");
        Node q = p.next;
        p.value = q.value;
        p.next = q.next;
        if (q == end) end = p;
        // q 由垃圾回收器释放（伪代码中：Free(Q)）
    }

    // 清空：Head ← End（其他结点由 GC 释放）
    void clear() { head = end; }

    // 有序插入：插在第一个更大的元素之前 – 多亏了哨兵，没有特殊情况
    void insertSorted(int x) {
        end.value = Integer.MAX_VALUE; // 哨兵是“无穷大” – 查找一定会停止
        Node p = head;
        while (p.value < x) p = p.next;
        insertBefore(p, x);
    }

    public static void main(String[] args) {
        SentinelList l = new SentinelList();
        System.out.print("empty: ");
        l.print();
        l.insertLast(3);
        l.insertLast(9);
        l.insertLast(4);
        l.insertFirst(1);
        System.out.print("insertLast 3, 9, 4; insertFirst 1: ");
        l.print();

        System.out.println("search(9) found? " + (l.search(9) != null) + ", search(7) found? " + (l.search(7) != null));

        l.insertBefore(l.search(9), 8);
        System.out.print("insertBefore(9, 8): ");
        l.print();

        l.delete(l.search(4)); // 删除最后一个真正的结点：哨兵“后退”一步
        System.out.print("delete(4): ");
        l.print();
        l.delete(l.search(1)); // 删除第一个结点：没有特殊情况
        System.out.print("delete(1): ");
        l.print();

        SentinelList s = new SentinelList();
        for (int x : new int[] { 5, 2, 8, 1, 9, 3 }) s.insertSorted(x);
        System.out.print("with sorted insertion: ");
        s.print();
        s.clear();
        System.out.println("empty after clear? " + s.isEmpty());
    }
}