結構陣列是一種很常用的資料結構，但它有一個很明顯的缺點…
#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 住啊啊～
