實作一下 linkedList::remove() 吧！

這個類別的功用是：給定一個目標值，從鏈結串列移除包含目標值的節點。

定義類別

class SLL {
private:
    SLLNode *head;
public:
    SLL();
    void pushFront(int);
    void printAll();
    int popFront();
    void pushBack(int);
    int popBack();
    void insert(int);
    void remove(int);
};

class DLL {
private:
    DLLNode *head, *tail;
public:
    DLL();
    void pushFront(int);
    void printAll();
    int popFront();
    void pushBack(int);
    int popBack();
    void insert(int);
    void remove(int);
};

單向鏈結串列

大致來說可以用三個步驟來描述：

1. 確認鏈結串列是否為空
2. 進到迴圈尋找目標值，並記錄該目標節點的前一項（prev）
3. 將 prev 的下一項設為目標節點的下一個節點

注意：如果目標節點為第一項，我們需要額外判斷，因為這會影響到 this -> head 的指向

void SLL::remove(int tg) {
    if (this -> head == NULL) 
        return ;
    if (this -> head -> data == tg) {
        SLLNode *tmp = this -> head;
        this -> head = this -> head -> next;
        delete tmp;
        return ;
    }
    SLLNode *cur = this -> head, *prev;
    while (cur) {
        if (cur -> data == tg) {
            prev -> next = cur -> next;
            delete cur;
            return ;
        }
        else {
            prev = cur;
            cur = cur -> next;
        }
    }
    return ;
}

雙向鏈結串列

void DLL::remove(int) 其實與 void SLL::remove(int) 大同小異，只是我們要特別注意「是否有將 prev 正確的連上」以及「若刪除的節點恰好是 head 或 tail」。

void DLL::remove(int tg) {
    DLLNode *tmp;
    if (this -> head == NULL) { // 鏈結串列為空
        return ;
    }
    if (this -> head -> data == tg) { // 目標節點為鏈結串列第一個節點
        tmp = this -> head;
        this -> head = this -> head -> next;
        if (this -> head == NULL) { // 考慮鏈結串列是否為空
            this -> tail = NULL;
            delete tmp;
            return ;
        }
        delete tmp;
        this -> head -> prev = NULL;
        return ;
    }
    if (this -> tail -> data == tg) { // 目標節點為鏈結串列第一個節點
        tmp = this -> tail;
        this -> tail = this -> tail -> prev;
        if (this -> tail == NULL) { // 考慮鏈結串列是否為空
            this -> head = NULL;
            delete tmp;
            return ;
        }
        delete tmp;
        this -> tail -> next = NULL;
        return ;
    }
    DLLNode *cur = this -> head;
    while (cur) { // 目標節點在鏈結串列中間
        if (cur -> data == tg) {
            tmp = cur;
            cur -> prev -> next = cur -> next;
            cur -> next -> prev = tmp -> prev;
            delete tmp;
            return ;
        }
        else {
            cur = cur -> next;
        }
    }
    return ; // 目標節點不存在於鏈結串列中
}   

上述的類別方法是建立於兩個條件：

1. 資料不重複
2. 非遞增的序列，即順序與大小並無關聯

可以分別試試實作「更改以上兩個條件」而得到的類別方法，其實不會太困難，原理是大同小異的。

下一篇，我們介紹鏈結串列最後一個部分：翻轉鏈結串列 linkedList::reverse()