有了 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);
};
想法很簡單,找到鏈結串列的最後一個節點,在他的後方新增一個節點就完成啦!
其中,最複雜的是「找到鏈結串列的最後一個節點」:
cur
cur -> next == NULL
才停止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;
}
}
不知道你會不會好奇為什麼我們還需要單向的鏈結串列?
在這個議題中,雙向鏈結串列確實比單向鏈結串列的速度還快!
但是雙向鏈結串列的節點所需要的記憶體空間較單向鏈結串列的節點還多(每一個節點都多紀錄一個指標變數),當鏈結串列包含很多節點時,記憶體用量差距明顯可見!
我只能說各有各的好處。