public class MyArrayList {//此為創(chuàng)建一個接口
    public int[] elem;
    public int usedSize;
    public static int capacity = 10;

    public MyArrayList() {
        this.elem = new int[capacity];//新建一個數(shù)組
    }
    public boolean isFull() {
        return this.usedSize == capacity;//判斷數(shù)組是否已滿
    }

    // 在 pos 位置新增元素
    public void add(int pos, int data) { //pos為要插入元素的下標(biāo)，data為要插入的數(shù)據(jù)
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法！");
            return;
        }
        //1、滿的情況   2、pos的合法情況
        if (isFull()) {
            //擴(kuò)容
            this.elem = Arrays.copyOf(this.elem, 2 * capacity);
            capacity *= 2;//新的容量
        }//此處調(diào)用前面 isfull（） 函數(shù)來判斷是否已滿，返回真，執(zhí)行if里面的語句，擴(kuò)容兩倍；若不滿，返回假，跳過if內(nèi)的語句。
        for (int i = this.usedSize - 1; i >= pos; i--) {
            this.elem[i + 1] = this.elem[i];
        }//在前面的代碼確定數(shù)組里面有盈余位置的情況下，將前一個數(shù)賦給后一個位置，從而騰出 pos 位置
        this.elem[pos] = data; //給pos 位置的函數(shù)賦我們想要的值（即data）
        this.usedSize++;//usedsize 是奇數(shù)器，pos位置增加一個數(shù)組，自然要算上
    }

    // 打印順序表
    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }// 此處使用for循環(huán)遍歷打印

    public boolean isEmpty() {
        return this.usedSize == 0;
    }//判斷數(shù)組是否為空

    // 判定是否包含某個元素
    public boolean contains(int toFind) {
        if (isEmpty()) return false;
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return true;
            }
        }
        return false;
    }//toFind 為我們要查找的元素，先判斷是否為空，再用循環(huán)遍歷判斷是否為該數(shù)

    // 查找某個元素對應(yīng)的位置
    public int search(int toFind) {
        if (isEmpty()) return -1;
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == toFind) {
                return i;
            }
        }
        return -1;
    }//這個查找和上面的那個判斷唯一的區(qū)別就是上面返回的是真與假，這個返回的是查到的那個數(shù)，本質(zhì)的方法都是一樣的

    // 獲取 pos 位置的元素
    public int getPos(int pos) {
        if (isEmpty()) {
            //return -1; 業(yè)務(wù)的處理
            throw new RuntimeException("順序表是空的");//手動拋出錯誤(異常)
        }
        if (pos < 0 || pos >= this.usedSize) {
            throw new RuntimeException("pos不合法");//手動拋出錯誤(異常)
        }

        return this.elem[pos];
    }//這個其實很簡單，只需排除一下空表和pos 不合法的情況，之后返回 elem[pos]的值就行

    // 獲取順序表長度
    public int size() {
        return this.usedSize;
    }

    // 給 pos 位置的元素設(shè)為 value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos不合法！");
            return;
        }
        if (isEmpty()) {
            System.out.println("順序表為空！");
            return;
        }
        this.elem[pos] = value;
    }//這個也簡單，只要判斷一下 數(shù)組是否不合法，是否為空，直接 this.elem[pos] = value就行了

    //刪除第一次出現(xiàn)的關(guān)鍵字key
    public void remove(int toRemove) {
        if (isEmpty()) return;
        int index = search(toRemove);
        if (index == -1) {
            System.out.println("沒有你要刪除的數(shù)字");
            return;
        }
        for (int i = index; i < this.usedSize - 1; i++) {
            this.elem[i] = this.elem[i + 1];
        }
        this.usedSize--;
    }
    //這里就是判斷數(shù)組是否為空，index 是否存在（此處調(diào)上面 search 函數(shù)），最后用for 循環(huán)遍歷，將后一個元素覆蓋在前一個元素上面

    // 清空順序表
    public void clear() {
        for (int i = 0; i < this.usedSize; i++) {
            this.elem[i] = 0;
        }
        this.usedSize = 0;
    }//用for循環(huán)遍歷每一個元素，將其賦值為 0 ，之后再將計數(shù)器 usedsized 也賦值為 0
}

class Node {//創(chuàng)建一個節(jié)點類
//一個節(jié)點是有兩個域或者多個域的，以下便是創(chuàng)建的兩個域
    public int val;//鏈表里面的數(shù)值
    public Node next;//這是一個引用變量，用于標(biāo)識每個鏈表單元的下一個數(shù)的地址，因為它存的是節(jié)點，而節(jié)點的類型就是Node，所以我們也用Node 來定義這個變量。

    public Node(int val) { //這是一個類里面的一個方法用來給鏈表當(dāng)中的val賦值
        this.val = val;//因為next存的hi下一個節(jié)點的地址，所以我們是不知道也不能賦值的
        }
}
//鏈表
public class MyLinkedList {//此處為創(chuàng)建鏈表的接口
     public Node head;//標(biāo)識單鏈表的頭節(jié)點（這也是一個引用變量）

    /**
     * 窮舉的方式 創(chuàng)建鏈表  當(dāng)然很low。此處只是為了好理解
     */
    public void createList() {
        Node node1 = new Node(12);//新建一個節(jié)點的對象node1，此為節(jié)點1，賦值為12
        Node node2 = new Node(3);//此為節(jié)點2，賦值3
        Node node3 = new Node(5);//此為節(jié)點3，賦值5
        Node node4 = new Node(2);//此為節(jié)點4，賦值6
        node1.next = node2;//node1中的next存node2（node2是一個對象的引用，存的是對象在堆中的地址）

        // 也就是說node1.next指向node2指向的地址

        node2.next = node3;//以下三個原理同上
        node3.next = node4;
        this.head = node1;//此處為定義一個head（后面head可能會有改動）

    }

    /**
     * 打印單鏈表
     */
    public void show() {
        Node cur = this.head;//將head的值暫時存到cur中，這樣就是單純地是cur在變，head值不改變
        while(cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;//通過這道程序?qū)ur依次向后移動最后到空的時候打印出來
        }
        System.out.println();
    }

    //得到單鏈表的長度
    public int size() {
        Node cur = this.head;//同樣地，此處還以cur為介質(zhì)向后移動
        int count = 0;
        while (cur != null) {
            count++;//4  cur 依次經(jīng)過各個節(jié)點的時候count便隨之計數(shù)
            cur = cur.next;
        }
        return count;
    }

    //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中 15
    public boolean contains(int val) {//這里函數(shù)參數(shù)中的val就是我們要查找的 key
        Node cur = this.head;
        while (cur != null) {//同樣的方法遍歷節(jié)點
            if(cur.val == val) {
                return true;
            }
            cur = cur.next;
        }
        return false;//如果遍歷完了都沒有找到那就肯定沒有了
    }



    //頭插法
    public void addFirst(int data) {//date為要插入的數(shù)據(jù)
        Node node = new Node(data);//此處為創(chuàng)建要插入的節(jié)點（對象）內(nèi)部存儲的值為 date
        if(this.head == null) {//判斷頭結(jié)點是否為空
            this.head = node;// 若為空，則根本沒有鏈表，直接將要插入的節(jié)點賦給head
        }else { //此為有鏈表存在的狀況
            node.next = this.head;//此處操作讓head原本指向的對象(節(jié)點)成為鏈表中的第二個節(jié)點
            this.head = node;
            //上面的操作讓head指向了node指向的節(jié)點(head是頭結(jié)點的標(biāo)志，自然要讓他移到第一位)
        }
    }


    //尾插法
    public void addLast(int data) {//data為要插入的數(shù)據(jù)
        Node node = new Node(data);//新建一個節(jié)點改值為data
        if(this.head == null) {//判斷鏈表是否為空，若為空，則為一個節(jié)點便也是最后一個
            this.head = node;//直接讓head指向node指向的節(jié)點即可
        }else {//若節(jié)點不為空時
            Node cur = this.head;//將head中的地址賦給中間變量cur
            while (cur.next != null) {
                cur = cur.next; //用cur遍歷節(jié)點
            }
            cur.next = node;//這是的cur已經(jīng)待在了最后一個節(jié)點上它的next上沒有東西了
                            //所以這個時候?qū)ode指向的地址交給next，既完成了節(jié)點的插入
        }
    }


    public Node searchPrev(int index) {
        Node cur = this.head;//同樣地，以 cur為介質(zhì)
        int count = 0;
        while(count != index-1) {
            cur = cur.next;//用cur 遍歷鏈表
            count++;
        }
        return cur;//此時返回的 cur剛好指向 index-1這個節(jié)點
    }

    //任意位置插入,第一個數(shù)據(jù)節(jié)點為0號下標(biāo)
    public void addIndex(int index,int data) {
        if(index < 0 || index > size()) {//判斷index是否合法
            System.out.println("下標(biāo)不合法");
            return;
        }
        //頭插法
        if(index == 0) {//index為0時，就是頭插法
            addFirst(data);
            return;
        }
        //尾插法
        if(index == size()) {//index為數(shù)組長度是就是尾插法
            addLast(data);
            return;
        }
        Node cur = searchPrev(index);//讓cur 拿到第index-1位置節(jié)點地址
        Node node = new Node(data);//創(chuàng)建一個存了數(shù)據(jù)為data 的節(jié)點
        node.next = cur.next;//將剛剛創(chuàng)建的節(jié)點中的next存進(jìn) cur 中的next(即把index的地址放到node的next里)
        cur.next = node;//再將node中存著的地址放到cur的next中
        //插中間歸根到底就是next的交換，以下為傳遞順序：
        //index-1中index的地址 ——> node.next
        //node的地址 ——> cur.next
    }

    //下面這段代碼用來找val的前驅(qū)節(jié)點
    public Node searchPrevNode(int val) {
        Node cur = this.head;//還是以 cur 為中間量
        while (cur.next != null) {//cur 遍歷至數(shù)組的最后一位
            if(cur.next.val == val) {//這里是判斷cur的下一個節(jié)點中的值是否為val
                return cur;//如果是的就返回cur
            }
            cur = cur.next;
        }
        return null;
    }

    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點
    public void remove(int val) {
        if(this.head == null) return;

        //單獨判斷頭節(jié)點的問題
        if(this.head.val == val) {
            this.head = this.head.next;
            return;//這段代碼的意思就是如果就是如果第一個節(jié)點中的值就是要刪除的值
            //那么直接就讓第一個節(jié)點的引用指向下一個節(jié)點，其實就是忽略第一個起到了一個刪除效果
            //而原來第一個節(jié)點變成了沒有人引用的對象會被jvm回收
        }
        Node cur = searchPrevNode(val);//拿到下一個節(jié)點值為val的cur
        if(cur == null) {//
            System.out.println("沒有你要刪除的節(jié)點！");
            return;
        }
        //下面就是cur 存在的情況
        Node del = cur.next;//創(chuàng)建一個節(jié)點del讓其使用cur中下一個節(jié)點的地址(也就是要刪的val地址)
        cur.next = del.next;//再把del中的存的下一個地址賦給 cur，那么就間接地抹去了val
    }
    //刪除所有值為key的節(jié)點
    public void removeAllKey(int val) {
        if(this.head == null) {//節(jié)點是否為空？
            return;
        }
        Node prev = this.head;//讓 prev指向 head指向的對象(prev本質(zhì)上就是前驅(qū)節(jié)點)
        Node cur = this.head.next;//讓 cur指向 head.next位置
        while (cur != null) { //用cur 來遍歷數(shù)組
            if(cur.val == val) { //
                prev.next = cur.next;//抹去要刪的節(jié)點
                cur = cur.next;//移動至下一個節(jié)點處
            }else {//以下是 cur處的值 不等于 val 的情況
                prev = cur;//將prev移到cur的位置
                cur = cur.next;//再將cur 向后移動
            }
        }
        //只有頭結(jié)點且頭結(jié)點便是要刪除的val的情況
        if(this.head.val == val) {
            this.head = this.head.next;
        }
    }
    public void clear(){

    }

}