图文版实现无头非循环单链表的增加和删除操作

hi，上一期已经给大家分享过代码版的链表的增删查改了，现在要对部分方法进行详细的介绍了

首先来说一说在任意位置的增加一个结点

废话不多说，开整

先来一幅图

加入已经有这样的链表了，现在要在 任意一个位置插入元素

我们先考虑一下

1.如果是在0下标插入，那么就直接调用头插法

2.如果在3下标插入，直接调用尾插法

3.在中间的位置插入

1.2比较简单，就不重复了

假如要在2下标插入一个结点，那就是要找2位置的前一个结点

 

//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index, int data) 

要先判定index位置是否合法

private  void isValid(int index) throws  IndexOutOfException{
    if(index<0||index>size()){
        throw new IndexOutOfException("index位置不合法");
        
    }
}

然后要找到index-1位置的结点

private Node findPlace(int index){
    Node cur=head;
    int count=0;
    while(count!=index-1){
        count++;
        cur=cur.next;
    }
    return cur;
}

然后我们看那个图，就是用node.next=cur.next,然后cur.next=node就完成了插入的操作

public void addIndex(int index, int data){
    Node node=new Node(data);
    Node cur=findPlace(index);
    node.next=cur.next;
    cur.next=node;


}

这个就写完了

下面再来说一说这个删除值为key的结点的方法

现在要删除值为27的结点，

 

这个图说明要找到要删除结点的前一个结点

private Node searchPlace(int key){
    Node cur=head;
    while(cur.next!=null){
        if(cur.next.val==key){
            return cur;
        }
        cur=cur.next;
    }
    return null;
}

 

然后是删除操作的实现

//删除第一次出现关键字为key的节点
public void remove(int key){
    if(head==null){
        return;
    }
    if(head.val==key){
        head=head.next;
        return;
    }
    Node cur=searchPlace(key);
    Node del=cur.next;
    cur.next=del.next;

}

如果是删除最后一个结点，也是上述做法

最后一个

//删除所有值为key的节点
public void removeAllKey(int key)

这个是最复杂的

上图

public void removeAllKey(int key) {
    if (head == null) {
        return;
    }
    Node prev = head;
    Node cur = head.next;
    while (cur != null) {
        if (cur.val == key) {
            prev.next = cur.next;
            cur = cur.next;
        } else {
            prev = cur;
            cur = cur.next;

        }

    }
    if(head.val==key){
        head=head.next;
    }
}

 

今天的讲解就到这里了，我们下期再见了，886！！！