作者：学Java的冬瓜
博客主页：☀冬瓜的博客🌙
专栏：Java-数据结构和算法
分享：不要去看别人的生活，去过自己的人生，我们每个人都有属于自己，独一无二的精彩。即使我们再平凡，我们也是限量版！
主要内容：单链表的插入删除

一、普通功能

1、节点定义

说明：节点的定义在这里使用了内部类的形式

    /**
     * 节点内部类
     * 说明：也可以另外定义一个类作为节点
     */
    static class ListNode {
        int value;
        //在C语言中，不能这样定义，因为它表示一个实实在在的结构体，会无限套娃
        //而Java中next是表示引用，它不指向对象时是null
        ListNode next; 

        // 注意：为了输入数据并且测试方便，使用了构造方法，而不使用创建链表的方方法去先创建一个链表
        public ListNode(int value) {
            this.value = value;
        }
    }

    private ListNode head; //默认初始化为null。

2、createList

说明：这是根据输入一组数，先创建一个链表，链表以exit字符串结束输入。

// 创建链表
    public void createList() {
        Scanner scanner = new Scanner(System.in);
        this.head = new ListNode();
        this.head.value = scanner.nextInt();
        this.head.next = null;

        ListNode cur = this.head;

        while(!scanner.hasNext("exit")) {
            ListNode newNode = new ListNode();
            newNode.value = scanner.nextInt();
            newNode.next = null;

            cur.next = newNode;
            cur = cur.next;
        }
    }

3、clear

// 销毁链表
    public void clear() {
        // Java中单链表可以直接把head置空，第一个节点置空后，被JVM回收
        // 第二个节点就没有引用再指向它，所以也被回收，所以
        // JVM依次从前往后回收链表的节点，从而实现链表的销毁
        this.head = null;
    }

4、display

//打印
	public void display() {
        ListNode cur = this.head;
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
    }

5、size

//计算单链表的长度
    public int size() {
        int size = 0;
        ListNode cur = this.head;
        //注意：不能开头size=1且cur->next != null，如果是空链表就会出问题，除非分类讨论
        while( cur!= null) {
            size++;
            cur = cur.next;
        }
        return size;
    }

6、contains

//查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while (cur != null) {
            if(cur.value == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

二、插入删除

1、addFirst

//头插法
    public void addFirst(int data) {
        // 创建了新节点，并完成初始化
        ListNode newNode = new ListNode(data);
        newNode.next = null;

        // 1、新节点连接在第一个节点的前面
        // 2、更新head头节点
        newNode.next = this.head;
        this.head = newNode;
    }

2、addLast

//尾插法
    public void addLast(int data) {
        // 1 给对象分配空间
        ListNode newNode = new ListNode(data);
        newNode.next = null;

        // 2 空链表
        if(this.head == null) {
            this.head = newNode;
        }
        // 3 链表至少有1个节点
        else {  
            ListNode cur = this.head;
            while (cur.next != null) {
                cur = cur.next;
            }
            
            // 4 找到尾节点,插入数据
            //出循环cur.next == null，即cur是最后一个节点
            cur.next = newNode;
        }
    }

3、addPos

功能：任意位置插入，pos表示第pos个位置

法一：利用函数获取第pos前一个节点

    //任意位置插入,第一个数据节点为1号下标
    public void addPos(int pos,int data) {
        // 1 合法性
        if(pos < 1 || pos > this.size()+1) {
            System.out.println("位置不合法");
        }
        
        // 2 头插
        if(pos == 1) {
            addFirst(data);
        }
        // 3 尾插
        else if (pos == this.size()+1) {
            addLast(data);
        }
        // 4 普通位置插入
        else {
            ListNode prev = findPosPrevNode(pos);
            ListNode newNode = new ListNode(data);

            newNode.next = prev.next;
            prev.next = newNode;
        }
    }
    // 5 找到并返回第pos的前一个节点
    private ListNode findPosPrevNode(int pos) {
        ListNode prev = this.head;
        // 注意:比如pos=3,循环只执行一次,所以找到第二个节点
        while (pos-1> 1) {
            pos--;
            prev = prev.next;
        }
        return prev;
    }

法二、利用节点prev和i的控制找到前一个节点

    //任意位置插入,第一个数据节点为1号下标
	public void addPos(int pos,int data) {
        //法一：
        //1、头插
        if(pos == 1) {
            addFirst(data);
        }else {
            //2、尾插+任意插
            // 注意:如果是带头节点，可以j从0开始计算，prev从头节点开始
            // 就不需要单独考虑头插的问题，下面代码就可完成任意位置插入
            ListNode newNode = new ListNode(data);
            newNode.next = null;

            int i = 1;
            ListNode prev = this.head;
            //理解: 如果位置是合法的, 那么出循环后i=pos-1, i表示的是第i个
            // 所以此时prev是第i个即第pos-1个节点
            while (prev != null && i<pos-1) {
                prev = prev.next;
                ++i;
            }
            // 3、合法性
            if(prev == null || i > pos-1) {
                System.out.println("位置不合法");
                return;
            }
            // 4、合法则插入
            newNode.next = prev.next;
            prev.next = newNode;
        }
    }

4、remove

法一：利用函数返回第一个value等于key的前一个节点

//删除第一次出现关键字为key的节点
    public void remove(int key) {
        // 1 空链表
        if(this.head == null) {
            return;
        }
        // 2 判断第一个节点的value是否等于key
        if(this.head.value == key) {
            this.head = this.head.next;
            return;
        }
        // 3 findPrevOfKey从第二个节点往后找
        // 如果找到就返回value值等于key节点的前一个节点
        ListNode prev = findPrevOfKey(key);
        if (prev == null) {
            System.out.println("没有你要删除的数");
        }else {
            prev.next = prev.next.next;
        }
    }
    // 4 找到并返回第一个value等于key节点的前一个节点
    private ListNode findPrevOfKey(int key) {
        ListNode cur = this.head;
        while (cur.next != null) {
            if (cur.next.value == key) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

法二：利用cur.next.value的判断方法

//删除第一次出现关键字为key的节点
    public void remove(int key) {
        //法一：一个一个判断
        //1、空链表
        if(this.head == null) {
            return;
        }
        // 2、判断第一个节点
        if(this.head.value == key) {
            this.head = this.head.next;
        }else {
            ListNode cur = this.head;
            //3、判断第二个到最后一个节点
            while (cur.next != null) {
                if(cur.next.value == key) {
                    cur.next = cur.next.next;
                    break;
                }

                cur = cur.next;
            }
        }
    }

5、removeAllKey

法一：最后处理头节点的value等于key的情况

    public void removeAllKey(int key) {
// 法一：最后处理链表开头有删除节点的情况
        // 注意：也可以开头不用while处理，先把第二个节点及之后的value等于key的节点删掉
        // 最后再来解决头节点value是否等于key的问题
        // 1 判断是否为空
        if(this.head == null) {
            return;
        }
        // 2 删除除头节点外的value等于key的节点
        ListNode cur = this.head.next;
        ListNode prev = this.head;  //注意：prev记录cur左边最靠近一个value不等于key的节点,头节点是删除节点不算在内
        while(cur != null) {
            if(cur.value == key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        // 3 判断头节点value等于key的情况
        //注意：上面的代码删掉了除第一个节点为value的其它节点，最后处理第一个节点
        if(this.head.value == key) {
            this.head = this.head.next;
        }
    }

法二：先处理开始节点value等于key的问题

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //法二:先用while处理开头有删除节点的情况
        // 1 先处理开头节点value等于key的问题
        while(this.head != null && this.head.value == key) {
            this.head = this.head.next;
        }

        // 2 判断此时链表是否为空链表
        // 注意要放在第一步的下面,不然可能出现本来不是空链表,删除后成为空链表的情况
        // 若:head==null,则完成删除
        if(this.head == null) {
            return;
        }

        // 3 判断从第一个不是value等于key的节点开始,后面的节点
        // 注意:此时head是第一个value不等于key的节点
        //且prev肯定不为null。 cur可能为null,cur为null则删除完成
        ListNode cur = this.head.next;
        ListNode prev = this.head;

        // 注意:相当于双指针,prev永远是cur的左边一个节点,cur在右边
        while(cur != null) {
            if(cur.value == key) {
                prev.next = cur.next;
            }else {
                // 重点：当cur的value！=key时，prev才能改变位置
                // 因为cur.value==key时，cur已经指向了下一个节点，下个节点的value可能也是key
                prev = cur;
            }
            cur = cur.next;
        }
    }