Linked List: 新增資料、刪除資料、反轉

Linked list. (完整範例程式碼也可以看這裡：Linkedlist.cpp). class ListNode 與 class LinkedList 的定義如下：. // C++ code #include using std::cout; ... Togglenavigation SecondRound Archives Tags About 先備知識與注意事項 本篇文章將延續LinkedList:Intro(簡介)，繼續介紹於Linkedlist中常見的操作：新增資料、刪除資料與反轉Linkedlist。

Linkedlist (完整範例程式碼也可以看這裡：Linkedlist.cpp) classListNode與classLinkedList的定義如下： //C++code #include usingstd::cout; usingstd::endl; classLinkedList;//為了將classLinkedList設成classListNode的friend, //需要先宣告 classListNode{ private: intdata; ListNode*next; public: ListNode():data(0),next(0){}; ListNode(inta):data(a),next(0){}; friendclassLinkedList; }; classLinkedList{ private: //intsize;//size是用來記錄Linkedlist的長度,非必要 ListNode*first;//list的第一個node public: LinkedList():first(0){}; voidPrintList();//印出list的所有資料 voidPush_front(intx);//在list的開頭新增node voidPush_back(intx);//在list的尾巴新增node voidDelete(intx);//刪除list中的intx voidClear();//把整串list刪除 voidReverse();//將list反轉:7->3->14=>14->3->7 }; 目錄 函式：PrintList 函式：Push_front 函式：Push_back 函式：Delete 函式：Clear 函式：Reverse 測試 參考資料 Linkedlist系列文章 函式：PrintList 第一個要介紹的是PrintList()，功能就是把Linkedlist中的所有資料依序印出。

要印出所有的資料，就必須「逐一訪問(Visiting)」Linkedlist中的每一個node，這樣的操作又稱為Traversal(尋訪)。

能夠完成這樣的操作，要歸功於node中記錄了「下一個node的記憶體位置」，如此，才能在訪問完當前的node之後，知道要繼續往哪一個記憶體位置上的node前進。

圖一。

以圖一為例： 建立ListNode*current來表示「目前走到哪一個node」。

若要對Linkedlist存取資料，必定是從第一個node開始，所以把current指向first所代表的記憶體位置，current=first。

目前first即為node(\(7\))。

同時，還能夠知道「下一個node」是指向node(\(3\))。

在印出current->data，也就是\(7\)後，便把current移動到「下一個node」。

透過current=current->next，即可把current指向node(\(3\))所在的記憶體位置。

重複上述步驟，直到current指向Linkedlist的終點NULL為止，便能印出所有資料。

由此可見，所有需要在Linkedlist中尋找特定資料的操作，都會用上Traversal。

程式範例如下： //C++code voidLinkedList::PrintList(){ if(first==0){//如果firstnode指向NULL,表示list沒有資料 cout<data<next; } cout<\(14\))的開頭加入\(23\)，方法如下： 先建立一個新的節點ListNode*newNode，帶有欲新增的資料(\(23\))，如圖二(a)。

將newNode中的pointer：ListNode*next，指向Linkedlist的第一個nodefirst，如圖二(b)。

接著，把first更新成newNode。

經過以上步驟(時間複雜度為O(\(1\)))便得到新的Linkedlist：\(23\)->\(3\)->\(14\)。

圖二(a)。

圖二(b)。

程式範例如下： //C++code voidLinkedList::Push_front(intx){ ListNode*newNode=newListNode(x);//配置新的記憶體 newNode->next=first;//先把first接在newNode後面 first=newNode;//再把first指向newNode所指向的記憶體位置 } 函式：Push_back Push_back()的功能是在Linkedlist的尾巴新增資料。

若考慮在Linkedlist(\(7\)->\(3\)->\(14\))的尾巴加入\(23\)，方法如下： 先建立一個新的節點ListNode*newNode，帶有欲新增的資料(\(23\))。

先利用如同PrintList()中提過的Traversal，把新建立的ListNode*current移動到Linkedlist的尾端，node(\(14\))，如圖三(a)。

有些資料結構會在classLinkedList中新增一項ListNode*last，記錄Linkedlist的最後一個node，那麼，Push_back()就不需要Traversal，可以在O(\(1\))時間內完成。

若沒有ListNode*last，就需要O(\(N\))的Traversal。

接著把current的nextpointer指向newNode，如圖三(b)。

即可得到新的Linkedlist：\(7\)->\(3\)->\(14\)->\(23\)。

圖三(a)。

圖三(b)。

程式範例如下： //C++code voidLinkedList::Push_back(intx){ ListNode*newNode=newListNode(x);//配置新的記憶體 if(first==0){//若list沒有node,令newNode為first first=newNode; return; } ListNode*current=first; while(current->next!=0){//Traversal current=current->next; } current->next=newNode;//將newNode接在list的尾巴 } 函式：Delete Delete(intx)的功能是要刪除Linkedlist中，資料為intx的node。

一共會有兩種情形，第一種是Linkedlist中確實有intx，第二種是沒有。

在第一種情況中，需要再特別考慮「intx位於first」的情況。

case1-1：要在Linkedlist(\(7\)->\(3\)->\(14\))中刪除具有\(3\)的node，見圖四(a)： 建立兩個在Linkedlist中移動的指標：*current以及*previous。

利用Traversal的概念，以ListNode*current指向node(\(3\))，以ListNode*previous指向node(\(3\))的「前一個node」，node(\(7\))。

接著，把previous的pointer指向current的pointer。

此處，即為以node(\(7\))記住node(\(14\))的記憶體位置。

再把current的記憶體釋放(若是使用new進行動態配置，就使用delete釋放)，還給heap。

關鍵就是，在整個Delete()的過程，只有node(\(3\))知道node(\(14\))的記憶體位置，所以在把node(\(3\))刪除之前，必須先透過node(\(3\))的pointer找到node(\(14\))，把node(\(14\))接到node(\(7\))上之後，才可以釋放node(\(3\))的記憶體位置。

圖四(a)。

case1-2：若要刪除具有\(7\)的node，而且node(\(7\))位於Linkedlist的第一個位置(也就是*first)，見圖四(b)： 需要把這個情況獨立出來的原因是，這個情況不會進行Traversal，所以ListNode*previous始終指向NULL，便不能呼叫其privatedata，若進行previous->next將會因為意圖對「無效的」記憶體位置進行存取，而產生像是「EXC_BAD_ACCESS」的錯誤(error)。

移除的方法： 只要將first向後移動至first->next。

再釋放current的記憶體位置即可。

若Linkedlist只有一個node，那麼first=first->next將會把first指向NULL。

圖四(b)。

case2：若Linkedlist中沒有要刪除的node，見圖四(c)： 若想要刪除\(8\)，但是Linkedlist(\(7\)->\(3\)->\(14\))沒有\(8\)，那麼在Traversal後，ListNode*current會一路走到Linkedlist的結尾，也就是NULL。

若Linkedlist本來就是空的，那麼建立的ListNode*current=first，current也會指向NULL。

以上這兩種情況，直接結束Delete()函式。

圖四(c)。

程式範例如下： //C++code voidLinkedList::Delete(intx){ ListNode*current=first, *previous=0; while(current!=0&&current->data!=x){//Traversal previous=current;//如果current指向NULL current=current->next;//或是current->data==x }//即結束whileloop if(current==0){//list沒有要刪的node,或是list為empty std::cout<next;//把first移到下一個node deletecurrent;//如果list只有一個node,那麼first就會指向NULL current=0;//當指標被delete後,將其指向NULL,可以避免不必要bug //return; } else{//其餘情況,list中有欲刪除的node, previous->next=current->next;//而且node不為first,此時previous不為NULL deletecurrent; current=0; //return; } } 函式：Clear Clear()的功能是清除整個Linkedlist。

方法如下： 從Linkedlist的「第一個node」first開始，進行Traversal。

利用first=first->next即可不斷移動first。

建立一個ListNode*current記錄「要刪除的node」之記憶體位置。

重複上述步驟，直到first指向Linkedlist的尾巴NULL為止。

見圖五(a)： 原先first記錄的是node(\(7\))。

建立ListNode*current記錄first，也就是node(\(7\))。

將first移動到node(\(3\))。

刪除current指向的node(\(7\))。

如此，便把node(\(7\))從Linkedlist移除。

圖五(a)。

見圖五(b)： 目前first記錄的是node(\(3\))。

建立ListNode*current記錄first，也就是node(\(3\))。

將first移動到node(\(14\))。

刪除current指向的node(\(3\))。

如此，便把node(\(3\))從Linkedlist移除。

圖五(b)。

見圖五(c)： 目前first記錄的是node(\(14\))。

建立ListNode*current記錄first，也就是node(\(14\))。

將first移動到NULL。

刪除current指向的node(\(14\))。

這樣便把Linkedlist的node刪除完畢。

圖五(c)。

程式範例如下： //C++code voidLinkedList::Clear(){ while(first!=0){//Traversal ListNode*current=first; first=first->next; deletecurrent; current=0; } } 函式：Reverse Reverse()的功能是反轉Linkedlist，以圖六(a)的Linkedlist為例，經過Reverse()之後，預期得到圖六(b)。

圖六(a)。

圖六(b)。

要倒轉Linkedlist，其實就是把每個node的pointer的方向前後對調，但是因為每個node都只有被Linkedlist中的「一個node」記得，例如圖六(a)，只有node(\(7\))記得node(\(3\))的記憶體位置，只有node(\(14\))記得node(\(8\))的記憶體位置，所以，如果把node(\(14\))的ListNode*next(原本指向node(\(8\)))更新成指向node(\(3\))，那麼整個Linkedlist中，就再也無法存取node(\(8\))。

所以在更新任何一個node之pointer之前，除了要知道「新的要指向的node」之記憶體位置，也要記錄「原先記錄的node」之記憶體位置，這裡使用三個指向node的指標，分別為previous、current、preceding，以圖六(c)為例： 目前current為node(\(3\))，其指標current->next指向的是node(\(14\))。

目前previous為node(\(7\))，是current->next最後要指向的記憶體位置。

目前preceding為node(\(14\))，避免current->next更新成node(\(7\))後，再也找不到node(\(14\))。

圖六(c)。

有了這三個指標後，要執行的步驟只有兩個： 將current->next從原本指向preceding更新成指向previous，如圖六(c)中圖。

執行current->next=previous，就把node(\(3\))的指向node(\(7\))。

把三個指標「按照順序」往前移動，然後進行下一個node之pointer調整，如圖六(c)下圖。

previous=current，將previous移動到node(\(3\))。

current=preceding，將current移動到node(\(14\))。

preceding=preceding->next，將preceding移動到node(\(8\))。

重複上述步驟，直到preceding更新成NULL，調整Linkedlist的first所指向的記憶體位置，即完成Linkedlist之反轉。

完整圖示見圖六(d)： 圖六(d)。

程式範例如下： //C++code voidLinkedList::Reverse(){ if(first==0||first->next==0){ //listisemptyorlisthasonlyonenode return; } ListNode*previous=0, *current=first, *preceding=first->next; while(preceding!=0){ current->next=previous;//把current->next轉向 previous=current;//previous往後挪 current=preceding;//current往後挪 preceding=preceding->next;//preceding往後挪 }//preceding更新成NULL即跳出whileloop current->next=previous;//此時current位於最後一個node,將current->next轉向 first=current;//更新first為current } 測試 在main()測試前面所介紹的各個函式。

//C++code intmain(){ LinkedListlist;//建立LinkedList的object list.PrintList();//目前list是空的 list.Delete(4);//list是空的,沒有4 list.Push_back(5);//list:5 list.Push_back(3);//list:53 list.Push_front(9);//list:953 list.PrintList();//印出:953 list.Push_back(4);//list:9534 list.Delete(9);//list:534 list.PrintList();//印出:534 list.Push_front(8);//list:8534 list.PrintList();//印出:8534 list.Reverse();//list:4358 list.PrintList();//印出:4358 list.Clear();//清空list list.PrintList();//印出:Listisempty. return0; } output: Listisempty. Thereisno4inlist. 953 534 8534 4358 Listisempty. 以上是在LinkedList中新增資料、刪除資料與反轉Linkedlist的方法介紹。

程式的實作方式根據classLinkedList的建立方式會有所不同，不過使用pointer的邏輯應該是大同小異的。

參考資料： IntroductiontoAlgorithms,Ch10 FundamentalsofDataStructuresinC++,Ch4 小殘的程式光廊：連結串列(LinkedList) LinkedList系列文章 LinkedList:Intro(簡介) LinkedList:新增資料、刪除資料、反轉 回到目錄： 目錄：演算法與資料結構 tags:C++,LinkedList,