如何建構Linked List

Sharon Peng

6 min readOct 20, 2019

相信在學C語言時，看到linked list 一定會很頭疼，每次學每次忘，這次是我第三次再度學習一次linked list，希望這次可以不要再忘記了～

首先，我想要建構一個「單向鏈結串列」

當我輸入1 時，把數字放進去linked list中
當我輸入2時，把數字印出來
當我輸入3時，把原本在裡面的數字刪掉。(前提是不會出現原本linked list 沒出現過的數字)

我想用分析程式碼的方式來跟大家解釋linked list

建構linked list 的首要條件就是要先建構一個struct

struct就像是一個我們自訂的資料型態（類似int之類的）

typedef struct listNode  // 
{
     int data;
     struct listNode * link;
 
} Node, *NodePtr;

linked list 從 NodePtr start 開始

NodePtr start = NULL; // initially there are no nodes// 進入insert function
insert (NodePtr *startPtr, int value);

＊我一開始一直卡在這個*startPtr，怎麼看也一直搞不懂為什麽要這樣寫，然後這樣寫程式一直出現記憶體配置錯誤的訊息。後來有比較懂一點了，但也不確定對不對，有錯還請各位多多指教。

我的想法是這樣的：

刪除我覺得比較簡單，所以就大略上寫一下。

刪除最前面的數，也跟下面的差不多。

這是我的程式碼：

#include<stdio.h>
#include<stdlib.h>typedef struct listNode
{
     int data;
     struct listNode * link;
 
} Node, *NodePtr;void insert(NodePtr *ptr, int value);
void del(NodePtr *ptr, int value);
void print(NodePtr ptr);int main()
{
    int num, data;
    NodePtr start = NULL; // initially there are no nodes   while(scanf("%d", &num)!= EOF)
   {
      switch(num)
      {
         case 1:
            scanf("%d", &data);
            insert(&start, data);
            break;
         case 2:
            print(start);
            break;
         case 3:
            scanf("%d", &data);
            del(&start, data);
            break;
      }
   }   return 0;
}
void insert(NodePtr *startptr, int value)
{
    NodePtr currentPtr = *startptr; // currentPtr's address is NULL
    NodePtr prePtr = NULL;     //建立新的Node來放入linked list中
    NodePtr newPtr= (NodePtr) malloc (sizeof(Node));; // new ptr
    newPtr->data = value;
    newPtr->link = NULL;     //判斷currentPtr的位址在哪邊
    while(currentPtr != NULL && value > currentPtr->data)
    {
         prePtr = currentPtr;
         currentPtr = currentPtr->link;
    } 
    if(prePtr == NULL) // 插入前面和empty的情況
    {
         printf("hello\n");
         newPtr->link = *startptr;
         *startptr = k;
    }
    else if(prePtr->link == NULL)  // 插入最後面
    {
         k->link = prePtr->link;
         prePtr->link = k;
    }
    else // 插入中間
    {
         prePtr->link = newPtr;
         newPtr->link = currentPtr;
    }
}void del(NodePtr *startptr, int value)
{
   // 刪除最前面的數
   if(value == (*startptr)->data) 
    {
         NodePtr tempPtr = *startptr;
         *startptr = (*startptr)->link;
         free(tempPtr);
    }
    else 
    {
         NodePtr currentPtr = *startptr;
         NodePtr prePtr = (*startptr)->link;         //把currentPtr指向輸入的那個數
         while(currentPtr != NULL && value != currentPtr->data)
         {
             prePtr = currentPtr;
             currentPtr = currentPtr->link;
         }         //刪除數字
         if(currentPtr->data == value && currentPtr->link != NULL)
         {
            prePtr->link = currentPtr->link;
            free(currentPtr);
         }
     }
}void print(NodePtr ptr)
{
     NodePtr temp = ptr;
     for( ; temp; temp = temp->link)
     {
          printf("%d ", temp->data);
     }
     printf("\n");
}

今天就先到這邊，希望大家都能明白我所做的解釋，我們下次見～～

如何建構Linked List

Written by Sharon Peng

No responses yet