[教學] Linked List / Linked List Sort－一個小小工程師的心情抒發天地

昨天在處理資料，剛好用到，為防老人痴呆，還是記在自己的blog裡面比較保險，免得以後有用到還要想一下推一下這樣 -_- ||

Linked List (鏈節串列)是什麼 ?

1. 就是連結串列，連結串列就是一堆一樣的東西串起來，一堆一樣的東西叫做結點 ( Node ) ，然後我們透過Pointer 連起來。

2. 在操作上比陣列彈性許多，像 : 加入 / 刪除，你可以在任何你想要的地方加入(Node) 和刪除 (Node) 。

3. Linked lsit 是在 "有需要的時候 "才 " 動態 " 配至記憶體空間。

4. 可以取代陣列儲存格式 ( 堆疊和佇列 )。

示意圖 :

int A [100] ={0} ;

在這100個，你可能只用了10個20個，Anyway ，只要你沒有用完，就是浪費，而相比之下，LinkedList 就能保證記憶體不被浪費。

※ 我們程式設計師能做的事情，是想辦法減少電腦的負擔，而製造麻煩是使用者在幹的。

※ Linked list 在某部分的功能其實優於Array許多，因為只需要改變一些Pointer即可，不過其實也要看使用的時機，如果資料式連續且單一的話，就別用linked list了 ( 改天可以考慮寫寫介紹vector ，這玩意 + Template 其實比Array還好用一些 (?) )。

接下來，我們來說說節點 ( Node ) 是什麼

1. Node 是linked list 非常重要的元素之一 ! ( 廢話.............. 但是也是實話 )

2. Node 是存放資料的地方

3. Node 是一個" 最少 "放兩個欄位的 " 結構 "

: 一個欄位放資料

: 一個欄位放 " 下一個節點的地址 " (很重要 )

節點的宣告

我們的linked list 長這樣

接下來，我們開始看code說故事吧 !

網路上大多數都是教用Struct來definition list node，在這我用class的方式，因為這樣更方便管理和定義，節省許多事情。

※這次教學內容 : 新增 / 清空 / 列印 / 排序 / 指定刪除

1.新增

2.刪除指定

3.清空

4.列印

5.排序 ( Use bubble sort )

Final :

Result :

Source code :

#include <iostream>
using namespace std;
//Definition list node
class Node
{
friend class LinkedList ;
private :

int value ; // Can be any type ,
Node *pNext ; // Pointer to the next Node

public :
   Node (void)
       : pNext (NULL)
   {}

   Node (int val)
       :value (val) , pNext (NULL)
   {}

   Node (int val,Node *next)
       : value (val) , pNext (next)
   {}
};

class LinkedList
{
private:
Node * pHead ;
Node * pTail ;

public :
   LinkedList (void) ;
   LinkedList (int val) ;
   ~LinkedList(void) ;

   void TailAppend (int val) ;       //Add new node to tail
   void Clear () ;                   //Clean
   void Print () ;                   //Print
   void BubbleSortList () ;       //Sort
   void Remove (int val);           //Remove
};

LinkedList::LinkedList ()
{
pHead = pTail = NULL ;
}

LinkedList::LinkedList(int val)
{
pHead = new Node (val) ;
pTail = pHead ;
}

LinkedList::~LinkedList()
{
   Clear() ;
}
void LinkedList::TailAppend(int val)
{
   if (pHead == NULL)
   {
       pTail = pHead = new Node (val) ;
   }
   else
   {
       pTail->pNext = new Node (val) ;
       pTail = pTail->pNext ;
   }
}

void LinkedList::Remove(int val)
{
Node *pPre = NULL , *pDel = NULL ;

   if (pHead->value == val )
   {
       pDel = pHead ;
       pHead = pDel->pNext ;
       delete pDel ;
       return ;
   }
   pPre = pHead ;
   pDel = pHead->pNext ;

   while (pDel != NULL)
   {
       if (pDel->value == val)
       {
           pPre->pNext = pDel->pNext ;
           if (pDel == pTail)
           {
               pTail = pPre ;
           }
           delete pDel ;
           break;
       }
       pPre = pDel ;
       pDel = pDel->pNext ;
   }
}

void LinkedList::Clear()
{
   Node *pDel = pHead ;
   while (pDel != NULL)
   {
       pHead = pHead->pNext ;
       delete pDel ;
       pDel = pHead;
   }
   pTail = pHead = NULL ;
}

void LinkedList::Print()
{
   Node *p = pHead ;
   if (pHead == NULL)
   {
       cout << "This list is empty"<<endl ;
       return ;
   }
   cout << "LinkedList : ";

   while (p!= NULL)
   {
       cout <<p->value << " " ;
       p = p->pNext ;
   }
   cout << endl ;

}

void LinkedList::BubbleSortList()
{
   Node *tail = pHead ;
   Node *tmp = pHead ;
   Node* curr = pHead;
   Node* prev = pHead;
   int size = 0;
   while(tail)
   {
       tail = tail->pNext;
       size++;
   }

   for(int i=size;i>0;i--)
   {
       curr = pHead;
       prev = pHead;
       for(int j=0;j<i-1 && curr->pNext;j++)
       {
           if(curr->value > curr->pNext->value)
           {
               tmp = curr->pNext;
               curr->pNext = tmp->pNext;
               tmp->pNext = curr;
               if(curr == pHead)
               {
                   pHead = tmp;
                   prev = tmp;
               }
               else
               {
                   prev->pNext = tmp;
                   prev = prev->pNext;
               }
           }
           else
           {
               curr = curr->pNext;
               if(j!=0) prev = prev->pNext;
           }
       }
   }
}

int main()
{
   LinkedList list;
   for (int i = 0 ; i < 10 ; i++)
   {
       int n = rand() %100 ;
       list.TailAppend(n) ;
   }
   cout << "Before Sort : "<< endl;
   list.Print();
   cout << endl <<"After Sort : "<<endl;
   list.BubbleSortList() ;
   list.Print();

   cout <<endl ;

   LinkedList list2;
   for (int i = 0; i< 10 ;i++)
   {
       list2.TailAppend(i) ;
   }
   list2.Print();
   list2.Remove(1) ;
   list2.Print();
   list2.Remove(3) ;
   list2.Print();
   list2.Remove(5) ;
   list2.Print();
   list2.Remove(9) ;
   list2.Print();
   list2.Remove(7) ;

}