今天我們要完成最後一個基本增減節點的類別方法：linkedList::popBack()

與上一篇相同的是我們可以來看看單雙向鏈結串列的差異。

定義類別

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

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

單向鏈結串列

想法跟 linkedList::pushBack() 大同小異

1. 宣告一個可變動的指標代表當前節點 cur
2. 宣告一個可變動的指標代表當前節點的前者 prev
3. 進入 while 迴圈，直到 cur -> next == NULL 才停止
4. 刪除 cur 指向的節點，因為這個節點是最後一個
5. 將 prev -> next 設為 NULL

int SLL::popBack()
{
    if (head == NULL) 
        return -1;
    int toBeReturn;
    if (head -> next == NULL)
    {
        toBeReturn = head -> data;
        delete head;
        head = NULL;
    }
    else
    {
        SLLNode *cur = head;
        SLLNode *prev;
        while (cur && cur -> next != NULL)
        {
            prev = cur;
            cur = cur -> next;
        }
        toBeReturn = cur -> data;
        delete cur;
        prev -> next = NULL;
    }
    return toBeReturn;
}

雙向鏈結串列

你可能發現了！這段程式碼跟 void DLL::popFront(int _data) 近乎相同！

為什麼？因為「雙向鏈結串列」紀錄著最後一個節點，因此我們不用透過迴圈找尋目標，就可以直接刪除鏈結串列最末端的節點。

這個類別方法同樣可以用三種情況來概括：

1. 鏈結串列為空
2. 鏈結串列只剩一個節點
3. 鏈結串列超過一個節點

int DLL::popBack()
{
    if (this -> tail == NULL)
    {
        return -1;
    }
    int toBeReturn;
    if (this -> head == this -> tail)
    {
        toBeReturn = this -> head -> data;
        delete this -> head;
        this -> head = NULL;
        this -> tail = NULL;
    }
    else
    {
        DLLNode *tmp = this -> tail;
        this -> tail = this -> tail -> prev;
        this -> tail -> next = NULL;
    }
    return toBeReturn;
}

四種基本增刪節點的操作已經介紹完畢，下一篇我們來介紹這四種操作的應用－－「堆疊與佇列」。