C 語言:鏈結串列(Linked List)的建立與刪除

結構陣列是一種很常用的資料結構,但它有一個很明顯的缺點…

#include <stdio.h>
 
struct girls{
  int age;
  char name[10];
};
 
int main(){
  girls TWICE[3] =
  {17, {'T', 'z', 'u', 'y', 'u', '\0'},
   19, {'M', 'i', 'n', 'a', '\0'},
   20, {'M', 'o', 'm', 'o', '\0'},
  };
  girls *ONCE = TWICE;
  for(int i = 0; i < 3; i++){
    printf("%d \n", ONCE[i].age);
    printf("%s \n", ONCE[i].name);
  };
  return 0;
}

 

我們宣告了一個結構,裡面有三個元素。

記憶體去儲存這個資料時,是依序放在記憶體裡面的。

如果我們想要在第一個元素和第二個元素之間、插入一個元素,比如在 Tyuzu 和 Mina 之間插入一個 Sana,要怎麼做呢?

為了保持原本的順序,必須把 Mina 和之後的 Momo 全部都往後移動,才能給 Sana 空出空間。

不覺得超級麻煩嗎…

為了解決這樣的問題,這邊來為大家介紹一個好用的資料結構——鏈結串列 (Linked List)。

 

鏈結串列 (Linked List)

利用指標,把原本的三個結構變數串起來。

在第一個結構後面加一個指標、讓它指向下一個結構;在第二個結構後面,再加一個指標,讓它指向下一個結構… 依次連接。

透過這樣的方式,能讓每個能彈性擴充。

當我們想在 Tzuyu 和 Mina 之間插入一個 Sana 時,就讓 Tzuyu 指向 Sana,再讓 Sana 指向後面 Mina。

鏈結串列的好處是彈性靈活,能動態跟記憶體要空間、或釋放空間。

鏈結串列,就是把陣列 (Array) 切成小塊,然後在裡面裝上追蹤器,不但更靈活、也更省記憶體空間呢!

這邊就要用到兩種運算元——NEW 和 DELETE 啦。

鏈結串列由以下元素構成:

  • 起始:指向鏈結串列第一個節點的指標
  • 鏈結串列的節點
    • 當前節點的資料
    • 下一個節點的地址
  • 結尾:最後一個節點連接的地址寫「NULL」,表示鏈結串列結束。

 

動態跟記憶體要空間: new, delete

我們平常都是事先宣告好所要使用的變數,當程式開始執行時,這些變數就會自動被配置記憶體空間。 比如 int 型就會被配置 4 個 byte 的記憶體空間。

然而有時有些變數並不知道何時會被使用,希望能在使用到的時候再配置空間給變數,所以我們可以動態的跟記憶體要空間、再在不需要後釋放掉它。

這裡用到的運算元分別是「new」與「delete」。

int *ptr = new int;

new 是用來跟記憶體要一個用來存放 4 個 byte 的 int 型變數所需要的空間,並傳回該空間的地址。我們再把地址存入指標 ptr 裡面。

如果要在配置完成後指定儲存值,可以這樣宣告:

int *ptr = new int(100);

要刪除這個空間,很簡單:

delete ptr;

 

我們也可以動態配置陣列:

int * ptr = new int[100];

表示跟記憶體要了 100 個 int 大小的空間,再回傳空間的第一個位址,存入指標 ptr 裡面。

要釋放掉這塊空間,就在 delete 後面加上 [] ,表示要釋放掉的是指標 ptr 後面的一塊陣列區域:

delete [] ptr;

 

把 NEW 和 DELETE 運用到鏈結串列上…

可以先建立一個結構,包含一個值 (value) 和一個指標 (pointer):

struct girl{
  int age;
  girl * next;
}

首先宣告一個指向 girl 型的指標 head,

然後用 new 跟記憶體要一塊 girl 類型的記憶體空間,並將這塊位址賦值給 head 指標。

girl * head;
head = new girl;

有了這樣的結構,我們就可以通過這種方式,來申請一片 girl 類型的記憶體儲存空間。

 

逐步創建鏈結串列

Step 1:建立第一個節點。

從第一節點開始,用 new 申請一塊 girl 類型的儲存空間,並且賦值——宣告一個 head 指標指向它。

為了建立後續的節點,我們宣告一個臨時的指標 current ,讓它指向新建立的節點、並表明我們現在正在哪,也就是 girl *current = head。

head = new girl;

girl * current = head;

 

Step 2:我們得先決定,要不要建立一個新的節點?

YES: 再申請一塊 girl 記憶體空間,所以 new girl 。再用剛剛宣告的指標,讓它的 next 指向下一個節點,變成 current -> next = girl; 。

同時,為了能夠建立後續的節點,得把 current 往前移動一個節點,使得 current 指向最新建立的節點,變成 current =current -> next;

current->next = new girl;

current = current->next;

建立完後,再次回到 Step 2 的問題,考慮要不要建立一個新節點。

YES 的話則和上述過程相同。

NO: 若不需要,那我們就要把最後節點指向下一個節點的 next 設定為 NULL。

current->next = NULL;

 

這個過程的完整程式碼寫下來就會是:

#include <stdio.h>

struct TWICE{
  int value;
  TWICE *next;
};

int main(){
  int count, i;
  scanf("%d", &count); //指定能有幾個節點
    
  TWICE *head = new TWICE(); //取得一個和 TWICE 大小一樣的區塊,然後配給 head 這個指標
  int age;
  scanf("%d", &age);

  //建立第一個節點
  head->value = age; //讀一個數字age進來,配給 head 的 value
  head->next = NULL; //第一個節點結束

  //建立後續的節點
  TWICE *current = head; //宣告現在只到哪裡的 current,先把它等於 head
  for( i = 1; i < count; i++){
    scanf("%d", &age);
    current->next = new TWICE();

    current = current->next;
    current->value = age;
    current->next = NULL; //建立節點完後,結束鏈結串列
  };

  //以下準備把linked list裡面的東西都印出來
  printf("Age of TWICE: ");
  current = head; //把current指回 head
  while(true){
    printf("%d ", current->value); //印目前的節點
    current = current->next; //印完後要印下一個節點的內容
    if (current == NULL){ //current為NULL的時候停下來
      break;
    }
  }
  printf("\n");
  return 0;
}

印出來的結果:

先指定有 3 個節點,接下來輸入 3 個數字作為三個節點的值,最後把結果印出來。

(´_ゝ`)… 有沒有覺得結果明明和陣列一樣,為什麼寫成鏈結串列,就這麼難呢?

在這邊還不能發揮鏈結串列真正的功用噢!如果只有這樣的話也不用特地寫成鏈結串列版了。

 

刪除節點

來試試看刪除節點吧!

Step 1:刪除的節點位於第一個位置。

由於是要刪掉第一個節點,直接讓 head 指向下一個節點就可以了,也就是 head->next 把 head 原本的值蓋掉,就已經完成刪除了。

但如果光只有這樣的話,並沒有把 head 原本的空間釋放出來。

所以我們先用一個 temp 把要被刪除的節點地址先存起來,再 head = head->next ,最後 delete temp 把這個節點佔用的記憶體空間釋放出來。

temp = head; //先把head值存起來
head = head->next; //把head指向下一個節點
delete temp; //把temp刪掉

Step 2:刪除中間的節點。

要刪除中間的節點,可以把前一個節點、直接指向它後一個節點。

但這樣有兩個問題:不知道第三個節點的地址是什麼怎麼指?指完後,那中間第二個節點的空間沒有釋放出來啊?

這時候就需要 2 個輔助的指標來幫助我們完成刪除。用 temp 指標來找這個要被刪除的節點。然後利用另外一個指標 follow 來跟在 temp 的後面。

最後再把 temp 指標 delete 掉,就成功釋放該節點了。

實際用程式碼寫出來,就會是:

  int find;
  scanf("%d", &find); //要被刪掉的值

  TWICE *temp, *follow;
  temp = head;

  if (head == NULL){  //head為空的空鏈結
    printf("Not found. \n"); //找不到
  }

  if(head->value == find){ //第一個節點是要刪除的目標值
    head = head->next; //把head移到下一格去
    delete temp; //刪掉存head值的temp
  }

  //尋找要刪除的目標,只要temp不為最後一格、且沒找到符合的值
  while((temp != NULL) && (temp->value != find)){ 
    follow = temp; //把temp和follow往下移動
    temp = temp->next;
  }
  if(temp == NULL){ //找到最後一格還沒找到
    printf("Not found. \n"); //印出找不到
  }
  else{
    follow->next = temp->next; 
    delete temp;
  }

來看看印出來的結果:

指定 5 個年紀 17, 18, 19, 20, 21 為 TWICE 鏈結串列的值。

然後指定要刪除 19,再印出來:

指定 4 個年紀 18, 19, 21, 20 為 TWICE 鏈結串列的值。

指定要刪除 35 (這當然不會是花樣年華少女的年紀呀),印出找不到。

 

如果想要能跑出上面結果的完整程式碼,附註在這邊歡迎拿去玩:

#include <stdio.h>

struct TWICE{
  int value;
  TWICE *next;
};

int main(){
  int count, i;
  scanf("%d", &count);
  int age;
  TWICE *head = new TWICE(); //取得一個和 TWICE 大小一樣的區塊,然後被給 head 這個指標

  scanf("%d", &age);
  head->value = age; //讀一個數字age進來,配給 head 的 value
  head->next = NULL; //第一個節點結束

  TWICE *current = head; //宣告現在只到哪裡的 current,先把它等於 head
  for( i = 1; i < count; i++){
    scanf("%d", &age);
    current->next = new TWICE();

    current = current->next;
    current->value = age;
    current->next = NULL; //建立節點完後,結束鏈結串列
  };

  //以下準備把linked list裡面的東西都印出來
  printf("Age of TWICE: ");
  current = head; //把current指回 head
  while(true){
    printf("%d ", current->value); //印目前的節點
    current = current->next; //印完後要印下一個節點的內容
    if (current == NULL){ //current為NULL的時候停下來
      break;
    }
  }
  printf("\n");

  int find;
  scanf("%d", &find); //要被刪掉的值

  TWICE *temp, *follow;
  temp = head;

  if (head == NULL){  //head為空的空鏈結
    printf("Not found. \n");
  }

  if(head->value == find){ //第一個節點是要刪除的目標值
    head = head->next;
    delete temp;
  }

  while((temp != NULL) && (temp->value != find)){ //尋找要刪除的目標
    follow = temp;
    temp = temp->next;
  }
  if(temp == NULL){
    printf("Not found. \n");
  }
  else{
    follow->next = temp->next;
    delete temp;
  }

  //做完後再把結果印一遍出來吧!
  printf("Age of TWICE: ");
  current = head; //把current指回 head
  while(true){
    printf("%d ", current->value); //印目前的節點
    current = current->next; //印完後要印下一個節點的內容
    if (current == NULL){ //current為NULL的時候停下來
      break;
    }
  }
  printf("\n");
  return 0;
}

今天的 Linked List 教學就到這邊結束啦!我們學會了利用 struct 來「建立」和「刪除」鏈結串列的方法。

大家是不是都會用了呢?

下一篇的鏈結串列教學,會來教如何把資料插入指定的位置!

 

來源:xkcd

(拍拍)指來指去超容易搞混亂 O_Q… 要 Hold 住啊啊~