不帶頭雙向連結清單删除指定元素

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（）列印所有元素的方法也需要自己寫