iT邦幫忙

2022 iThome 鐵人賽

DAY 11
0
Software Development

用C++ 設計程式中的系統櫃系列 第 11

[Day 11] 用C++ 設計程式中的系統櫃:linkedList::pushBack()

  • 分享至 

  • xImage
  •  

有了 linkedList::pushFront() 我們也需要一個 linkedList::pushBack()
從這個類別方法中,我們可以很明顯的發覺「單向鏈結串列」與「雙向鏈結串列」的差異!


定義類別

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

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

單向鏈結串列

想法很簡單,找到鏈結串列的最後一個節點,在他的後方新增一個節點就完成啦!
其中,最複雜的是「找到鏈結串列的最後一個節點」:

  1. 宣告一個可變動的指標代表當前節點 cur
  2. 進入 while 迴圈,直到 cur -> next == NULL 才停止
  3. cur -> next 處新增一個節點
void SLL::pushBack(int _data)
{
    if (this -> head == NULL) // 鏈結串列為空
    {
        this -> head = new SLLNode(_data);
        this -> head -> next = NULL;
    }
    else 
    {
        SLLNode *cur = this -> head;
        while (cur && cur -> next != NULL) 
        {
            cur = cur -> next;
        }
        cur -> next = new SLLNode(_data);
    }
}

為什麼要判斷 cur != NULL
雖然我們的目的是 cur -> next != NULL ,但是我們要先確保 cur 不是指向空指標,否則會給出錯誤訊息,而非簡單地跳出迴圈而已。


雙向鏈結串列

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

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

void DLL::pushBack(int _data)
{
    if (this -> tail == NULL)
    {
        this -> tail = new DLLNode(_data);
        this -> head = this -> tail;
    }
    else
    {
        this -> tail -> next = new DLLNode(_data);
        this -> tail -> next -> prev = this -> tail;
        this -> tail = this -> tail -> next;
    }
}

不知道你會不會好奇為什麼我們還需要單向的鏈結串列?
在這個議題中,雙向鏈結串列確實比單向鏈結串列的速度還快!
但是雙向鏈結串列的節點所需要的記憶體空間較單向鏈結串列的節點還多(每一個節點都多紀錄一個指標變數),當鏈結串列包含很多節點時,記憶體用量差距明顯可見!

我只能說各有各的好處。


上一篇
[Day 10] 用C++ 設計程式中的系統櫃:linkedList::popFront()
下一篇
[Day 12] 用C++ 設計程式中的系統櫃:linkedList::popBack()
系列文
用C++ 設計程式中的系統櫃30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言