[数据结构与算法]【数据结构】链表的插入删除

写链表的时候，必须保证引用不为空引用。像cur.next！=null，这种代码得保证cur不为空。

1 链表插入

1.1 不带傀儡结点的插入

1.1.1 插入到链表的中间位置

注：(只变化next存放的地址 需要找到待插入节点前一个位置)

例如:把100这个节点插入到1和2之间

把100这个节点插入到1和2之间，此时需要先知道1（待插入位置的前一个节点）这个节点的引用

• 定义一个prev引用，里面存放1的地址
  Node pre=new Node（1）；
• 定义一个cur引用，里面存放新节点的地址
  Node cur=new Node（100）；
  关键代码：

1.先修改cur.的指向，让cur指向2（即cur.next存放2的地址）
cur.next=prev.next;
2.pre 指向cur（pre的next存放cur的地址）
prev.next=cur;

1.1.2 头节点插入（插入到链表的头结点，使之为头结点）

注：头结点插入会影响head指向，之前的插入中间位置，需要找到待插入位置的前一个位置。但是头插前面没有位置

关键代码：
1.先让cur的next指向head
cur.next=head;
2.再让head指向新节点
head=cur;

1.3 尾插和中间插的（插入）关键代码相同（要找到末尾结点）

思路：先找到末尾结点，然后进行插入

    public static void  insertTail(Node head,int val){
        if (head==null){
            return ;
        }
        //先找到最后一个结点的位置
        Node prev=head;
        while(prev.next!=null){
            prev=prev.next;
        }
        //此时prev指的是最后一个元素
        
        //定义一个带插入的节点
        Node cur=new Node(10);
        cur.next=prev.next;
        prev.next=cur;
        
    }

1.2 带傀儡结点的插入

注：不带傀儡结点的链表，插入中间位置和插入头部是两种不同的代码。
带傀儡结点插入把两个操作统一。
此时的头插也相当于中间插.

1.2.1 中间插（要找到待插入结点前一个结点的位置）

public class Main {
    public static void main(String[] args) {
       Node head= createListWithDummy();

       //找到待插入前一个位置
        Node prev=head.next;
        //创建带插入的节点
        Node cur=new Node(10);
        //中间插的步骤
        //往中间结点插入，1和2之间
        cur.next=prev.next;
        prev.next=cur;

    }

    //带傀儡结点链表
    //傀儡借点中的值不使用
    //默认为链表长度是4
    private static Node createListWithDummy() {
        Node dummy=new Node(100);
        Node a=new Node(1);
        Node b=new Node(2);
        Node c=new Node(3);
        Node d=new Node(4);

        dummy.next=a;
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=null;
        return  dummy;
    }
}

1.2.2头插

注：插入到所有元素之前，也就是傀儡结点的后面

关键代码：
cur.next=prev.next;
prev.next=cur;

public class Main {
    public static void main(String[] args) {
       Node head= createListWithDummy();

      /* //找到待插入前一个位置
        Node prev=head.next;
        //创建带插入的节点
        Node cur=new Node(10);
        //中间插的步骤
        //往中间结点插入，1和2之间
        cur.next=prev.next;
        prev.next=cur;
*/
        //待插入前的节点为head
         Node prev=head;
        //创建带插入的节点
        Node cur=new Node(10);
        //头结点插入
        cur.next=prev.next;
        prev.next=cur;


    }

    //带傀儡结点链表
    //傀儡借点中的值不使用
    //默认为链表长度是4
    private static Node createListWithDummy() {
        Node dummy=new Node(100);
        Node a=new Node(1);
        Node b=new Node(2);
        Node c=new Node(3);
        Node d=new Node(4);

        dummy.next=a;
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=null;
        return  dummy;
    }
}

总结

1.带傀儡结点的头结点插入和中间插插入，代码相同

2.不带傀儡结点的头插和尾插

2.链表的删除

2.1不带傀儡结点

2.1.1 删除中间结点（找到前一个结点位置）

remove() 返回新的head的位置。

关键代码：prev.next=toDelete.next

2.1.1.1 按值删除

 //删除结点，按值删除
    public static Node remove(Node head,int value){
		if(head==null){
		return null;
       }
       if(head.val==value){
		//要删除的结点是头结点
			head=head.next;
			return head;
}
        //1.先找到val值对应位置的前一个位置
       Node prev=head;
       while(prev !=null && prev.next!=null && prev.next.val != value){
           prev=prev.next;
       }
       //循环结束，prev指向待删除节点的前一个
       if(prev==null && prev.next==null){

           return head ;
       }

       //2.进行删除，先找到待删除的结点
        Node toDelete=prev.next;
       prev.next=toDelete.next;
       return head;


    }

2.1.1.2 按位置删除

//删除结点，按照位置来删除
    //删除结点，按照位置来删除
    public static Node remove(Node head,Node toDelete){
        if(head==null){
            return null;
        }
        if(head==toDelete){
            //要删除的是头结点
            head=head.next;
            return head;
        }
        //1.先需要找到toDelete的前一个节点
        Node prev=head;
        while(prev !=null && prev.next!=toDelete){
            prev=prev.next;
        }
        if(prev==null){
            //没找到
            return null ;
        }
        //2.进行删除
        prev.next=toDelete.next;
        return head;
    }

2.1.1.3按下标删除

public static  Node remove(Node head,int index){

        if(index<0 || index>size(head)){
            return null;
        }
        //如果index为0；删除头结点
        if(index==0){
            head=head.next;
            return head;
        }
       //1.找到待删除结点的前一个位置，index-1就是这个位置
        Node prev=head;
        for(int i=0;i<index-1;i++){
            prev=prev.next;
        }
        //循环结束之后，prev就指向待删除结点的前一个位置
        Node toDelete=prev.next;
        prev.next=toDelete.next;
        return head;

    }

尾删

//针对不带傀儡结点链表，进行尾删
    public static Node removeTail(Node head){
        if(head==null){
            return null;
        }
        if(head.next==null){
            //此时连表里面只有一个元素，尾删就是链表本身
            //此时链表只有head一个结点，删除该节点之后，这个链表就变成空链表了
            return null;
        }
        //需要找到位结点的前一个结点
        //尾结点的next是空，尾结点的前一个结点是尾结点的next的next为空
        Node prev=head;
        while(prev!=null && prev.next!=null && prev.next.next!=null){
            prev=prev.next;
        }
        
        Node toDelete=prev.next;
        //接下来删除
        prev.next=toDelete.next;
        
        return head;

    }

2.1.2 删除链表的头结点

最关键的代码：head=head.next;

2.2带傀儡结点(不常用）

   public static void removeWithDummy(Node head,int val){
        //此时不需要考虑到head引用修改的问题，也不必单独考虑删除第一个结点
        //此时头删，中间删
        Node prev=head;
        while(prev!=null &&prev.next!=null && prev.next.val!=val){
            prev=prev.next;
        }
        //当这个循环结束，要么prev如果达到了链表末尾，要没找到了 val匹配的值
        if(prev==null || prev.next==null){
            //没有找到对应的结点
            return;
        }
        //找到了对应的结点
        Node toDelete=prev.next;
        prev.next=toDelete.next;
        return;

    }

总结：

不带傀儡结点的删除，头删和中间删，删除方式不一样。
带傀儡节点的删除，头删和中间删，山出发那个是相同