博客

不带头双向链表删除指定元素

1、remove（key）

对于remove（key），只需要删除第一次找到的元素，然后返回即可。

要删除指定元素，先要判断链表是否为空，如果链表为空，就不存在删除指定元素；如果不为空，接下来再判断要删除的元素是否是其头部。如果是其头部，将其头部后移，并将头的prev置为null；结构图如下：



如果不是头部，再向后找指定元素，如果要删除的结点是中间结点，结构图如下：



如果删除的是尾节点，又是另外一种情况



在上面的这三种情况中，删除头节点和尾节点需要特殊考虑一下

程序如下：

public int remove(int key) throws InterruptedException {
        if (this.head==null){
            return -1;
        }
        Node cur=this.head;
        int oldData=0;
        while(cur!=null){
            if (cur.data==key){
                if (cur==this.head){
                    //说明删除的是头结点
                    oldData=this.head.data;//记录要删除的值
                    head=head.next;//将头结点后移
                    head.prev=null;//前驱置为null
                }else {
                    //说明删除的不是头结点
                    cur.prev.next = cur.next;
                    if (cur.next !=null) {
                        //说明删除的不是尾结点
                        cur.next.prev =cur.prev;
                    } else {
                        //说明删除的是尾结点
                        this.last = cur.prev;
                    }
                    oldData=cur.data;
                }
                return oldData;
            }
            cur=cur.next;
        }
        return -1;
    }

测试：

public class TestDouble {
    public static void main(String[] args) throws InterruptedException {
        DoubleLinkedListImpl doubleLinkedList=new DoubleLinkedListImpl();
        doubleLinkedList.addFirst(1);
        doubleLinkedList.addFirst(2);
        doubleLinkedList.addFirst(3);
        doubleLinkedList.addFirst(4);
        doubleLinkedList.addLast(1);
        doubleLinkedList.addLast(2);
        doubleLinkedList.addLast(1);
        doubleLinkedList.addLast(4);
        doubleLinkedList.display();
        doubleLinkedList.remove(1);
        doubleLinkedList.display();
           }
}

结果：



在这个删除指定元素的程序中，里面的头插元素需要自己写，display（）打印所有元素的方法也需要自己写