public class SingleLinkedList {
      static class List{
        int item;   //	存儲(chǔ)數(shù)據(jù)
        List next;   //	指向下一個(gè)結(jié)點(diǎn)
        public List(int item) {
            this.item = item;
        }
        public List() {};
    }
//各種鏈表實(shí)現(xiàn)方法
//頭插法
public void addFirst(int data){
} 
    //尾插法
public void addLast(int data){
} 
    //任意位置插入,第一個(gè)數(shù)據(jù)節(jié)點(diǎn)為0號(hào)下標(biāo)
public void addIndex(int index,int data){
} 
    //查找是否包含關(guān)鍵字key是否在單鏈表當(dāng)中
public boolean contains(int key){
return false;
} 
    //刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
public void remove(int key){
}
    //得到單鏈表的長(zhǎng)度
public int size(){
    return -1;
}
    //鏈表的清空
public void clear() {
}
    //展示鏈表
public void display() {}

public void show() {
        //這里不是定義了一個(gè)節(jié)點(diǎn) 這里只是一個(gè)引用
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

 public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            //如果val值 是引用類(lèi)型  那么這里得用equals來(lái)進(jìn)行比較！??！
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

public void clear() {
        //將所有結(jié)點(diǎn)都置空，更為安全
        while (head != null) {
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
    }

public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

 public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //cur 指向的節(jié)點(diǎn)就是尾巴節(jié)點(diǎn)
        cur.next = node;
    }

 public void addIndex(int index,int data){
        int len = size();
        //0、判斷index位置的合法性
        if(index < 0 || index > len) {
            throw new IndexOutOfBounds("任意位置插入數(shù)據(jù)的時(shí)候，index位置不合法: "+index);
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == len) {
            addLast(data);
            return;
        }
        //1、先找到index-1位置的節(jié)點(diǎn)
        ListNode cur = findIndex(index);
        //2、進(jìn)行插入
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
}

 public ListNode findIndex(int index) {
        ListNode cur = head;
        while (index - 1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;//index-1位置的節(jié)點(diǎn)
    }

//刪除第一次出現(xiàn)關(guān)鍵字為key的節(jié)點(diǎn)
    public void remove(int key){
        if(head == null) {
            return;
        }
        //當(dāng)刪除結(jié)點(diǎn)為頭結(jié)點(diǎn)
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode prev = searchPrev(key); //返回待刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)
        if(prev == null) {
            System.out.println("沒(méi)有這個(gè)數(shù)據(jù)！");
            return;
        }
        ListNode del = prev.next;
        prev.next = del.next;
    }
    private ListNode searchPrev(int key) {
        ListNode prev = head;
        while (prev.next != null) {
            if(prev.next.val == key) {
                return prev;
            }else {
                prev = prev.next;
            }
        }
        return null;
    }

public void searchPrev(int num,int date) {
        ListNode prev = head;
       for(int i=0;i<num-1;i++) {
                prev = prev.next;  
        }
        prev.val=date;
    }