[資料結構(Data Structure, DS) 教學 教程 教材 Tutorial] 單向鏈結串列(Single Linked List)
YehYeh\'s Notepad yehyeh@gmail.com 

鏈結串列(Linked List)

單向鏈結串列(Single Linked List)

  • 單向鏈結串列(Single Linked List)
      • 由一組節點(Node)組成的有序串列
      • 每個節點由資料欄和一個鏈結欄(Link, Point)組成
      • 鏈結欄指向其它Node的位址
      • 首結點:第一個Node
      • 回收串列的時間為O(n),n為結點數 單向鏈結串列(Single Linked List)示意圖
  • Operations
    • Create List:建立串列
      • 建立一個空的鏈結串列 建立首節點
      struct Node {
          int data;
          Node *next;
      };
      
      Node *first;        //宣告首節點
      first = new Node;   //實體化首節點
      first->next = 0;    //指向null
      first->data = -1;
      
      struct Node {
          int data;
          struct Node *next;
      };
      
      struct Node *first = NULL ;
      first = malloc( sizeof(struct Node) );
      first->next = 0;    //null pointer
      first->data = -1;
      
      int Fibonacci(int n)
      {
          if( n <= 1 )
              return n;
      
          int fa = 0, fb = 1, fn;
          for(int i = 0; i <= n; i++){
              fn = fa + fb;
              fa = fb;
              fb = fn;
          }
          return fi;
      }
      
      class Node
      {
          public int data;
          public Node next;
      }
      
      Node first = new Node();
      
    • Insert Node:插入節點
      • 可分為:
        • 前端插入(insertFront):將新節點插入到串列最前端,並取代首節點 鏈結串列(Linked List) 前端插入
        • 中間插入(insert):將新節點插入到指定點後面 鏈結串列(Linked List) 中間插入
        • 尾端插入(append):將新節點插入到串列最尾端 鏈結串列(Linked List) 尾端插入
      struct Node** insert(Node **first, Node *ptrBeforeNode, int data)
      {
          Node* newNode = new Node;
          newNode->data = data;
          newNode->next = NULL;
          if(ptrBeforeNode == NULL){              // 插入在首節點之前
              newNode->next = *first;
              *first = newNode;
          }else{
              if(ptrBeforeNode->next == NULL)     // 插入在尾節點之後
                  ptrBeforeNode->next = newNode;
              else{                               // 插入在指定節點之後
                  newNode->next = ptrBeforeNode->next;
                  ptrBeforeNode->next = newNode;
              }
          }
      }
      
      insert(&first, NULL, 10);
      
      Node *createNode(void)
      {
          Node *tmpNode;
          tmpNode = (Node *) malloc(sizeof(Node));
          if(tmpNode == NULL){
              printf("記憶體不足");
              exit(1);
          }
          return (tmpNode);
      }
      
      void insert(Node *first, Node x){
          Node tmp;
          MALLOC(tmp, sizeof(*tmp));
          tmp->data = 50;
          if(*first){
              tmp->link = x->link;
              x->link = tmp;
          }else{
              tmp->link = NULL;
              *first = tmp;
          }
      }
      
      Node *insertNode( Node *first, Node *theNode, int data)}{
          Node *newNode;
          newNode = createNode();
          newNode = data;
          newNode->link = NULL;
          if( theNode == NULL ){            //前端插入
              newNode->link = first;
              first = new;Node;
          }else{
              if(theNode->link == NULL)    //尾端插入
                  theNode->link = newNode;
              else{                           //中間插入
                  newNode->link = theNode->link;
                  theNode->link = newNode;
              }
          }
          return (first);
      }
      
      public void insertFront()
      {
          Node newNode = new Node();
          newNode.link = first.link;
          first.link = newNode;
      }   
      
    • Find Node:尋找節點
      • 自指定節點開始往後依序循找符合的節點
      //搜尋指定節點
      struct Node* searchNode(struct Node *first, int searchData) {
          Node *curNode = first;
          while(curNode) {
              if(curNode->data == searchData)
                  return curNode;
              curNode = curNode->next;
          }
          cout << "Not Find " + searchData << endl;
      }
      
      Node findNode(Node *head, int data){
          Node *node;
          node = first;                   //由首節點開始搜尋
          while( node != NULL ){          //走訪串列
              if( node->data == data ) //若找到,則回傳
                  return node;
              node = node->link;       //指向下一個節點
          }
          return node;
      }
      
      /* 計算指定節點之後的長度 */
      int length( Node theNode ){
          int nodeNum = 0;
          Node *nextNode = theNode->link;
          while(nextNode != NULL) {
              nodeNum ++;
              nextNode = nextNode->link;
          }
          return (nodeNum);
      }
      
    • Delete Node:刪除節點
      • 邏輯性移除(Logically Remove):
        • 將要刪除的Node指標斷掉,無法透過鏈結串列找到該Node
      • 實際移除(Physically Delete):
        • 實際移除(Physically Delete):要刪除的Node從記憶體中移除
        鏈結串列(Linked List) 刪除節點
      bool deleteNode(struct Node **first, Node *ptrDelNode){
          Node *curNode = *first;
          if(ptrDelNode == *first){    //如果是首節點
              *first = curNode->next;
              delete ptrDelNode;
              return true;
          }
      
          while(curNode){              //如果不是首節點
              if(curNode->next == ptrDelNode){
                  curNode->next = ptrDelNode->next;
                  delete ptrDelNode;
                  return true;
              }
              curNode = curNode->next;
          }
          return false;
      }
      
      void *freeNode(Node *tmpNode){
          free(tmpNode);
      }
      
    • Reverse Linked List:串列反轉
      • 將串列節點的順序顛倒
      struct Node* reverse(struct Node** List){
          Node *parentNode = *List;
          Node *curNode = parentNode->next;
          Node *childNode = curNode->next;
      
          parentNode->next = NULL;
          while(childNode) {
              curNode->next = parentNode;
              parentNode = curNode;
              curNode = childNode;
              childNode = childNode->next;
          }
          curNode->next = parentNode;
          *List = curNode;
          return *List;
      }
      
    • Copy Linked List:複製串列
      • 將指定的串列複製到新的串列
      void copyLinkedList(struct Node *node, struct Node **ptrNewFirstNode)
      {
          if(node != NULL) {      //若要複製的串列不為空串列
              *ptrNewFirstNode = new Node;
              (*ptrNewFirstNode)->data = node->data;
              (*ptrNewFirstNode)->next = NULL;
              copyLinkedList(node->next, &((*ptrNewFirstNode)->next));
          }
      }
      
    • Compare Linked List:串列比較
      • 比較指定的2個串列
      int compareLinkedList(struct Node *node1, struct Node *node2)
      {
          static int flag;
          if(node1 == NULL && node2 == NULL) {
              flag = 1;
          } else {
              if(node1 == NULL || node2 == NULL) 
                  flag = 0;
              else if(node1->data != node2->data) 
                  flag = 0;
              else
                  compareLinkedList(node1->next, node2->next);
          }
          return flag;
      }
      
    • Delete Linked List:刪除串列
      • 刪除指定的串列
      void deleteLinkedList(struct Node **node)
      {
          struct Node *tmpNode;
          while(*node) {
              tmpNode = *node;
              *node = tmpNode->next;
              delete tmpNode;
          }
      }
      
    • Linked List Length:取得串列長度
      • 計算指定串列的長度
      int length(struct Node *startNode){
          int num = 0;    
          while(startNode != NULL){
              num++;
              startNode = startNode->next;
          }
          return num;
      }
      
    • Release List:回收串列
      • 為避免解構Node的浪費,可用一個List(Available List)存放已不使用的Node
      • 刪除Node或List時,將Node移到AV,而不真正的Delete(邏輯性移除)
      • 插入Node時,由AV中取出一個Node來插入,AV中沒有Node再用New
    • Display Linked List :顯示串列的內容
      • 顯示串列的內容
      void display(struct Node *first) {
          Node *list = first;
          while(list) {
              cout << list->data << " ";
              list = list->next;
          }
          cout << endl; 
      }