[資料結構] 鏈結串列教學[1]: 新增與印出
簡介
鏈結串列，英文為 linked list，是一種資料結構結構型態，我們可以藉由鏈結串列把資料一個一個串在一起，相較於陣列有著更彈性的增減數據的方式。
實作
首先，我們先來定義結構變數，在大部分的鏈結串列教學當中，最常見的其實就是結構裡便包含一個 data 的變數以及一個由自己本身宣告的 node 的指標變數，所以這裡我們宣告了一個 int data
int data;另外一個 struct node *next，這裡命名為 next 代表連結到下一個 node 的意思。
struct node *next;定義玩結構後，我們來宣告第一個結點，我們將其賦值為 5 ，並且暫時讓它不只向下一個結點
接著我們再宣告一個 node ，這裡我們稱它為 node2，賦值為 128，並讓 head 指向這個 node
我們接下來再宣告一個 node ，這裡我們稱它為 node3，賦值為 41，並且讓 node2 指向 node3
我們現在已經有了三個結點的鏈結串列，這時候我們可以把它們的數值都硬出來，來確保這些鏈結串列有符合我們的設定
這裡我們先動態宣告一個 current 結點
Node *current = (Node*)malloc(sizeof(Node));再來我們讓這個結點等同於head
current = head;我們知道，node3 的下一個結點指向是 NULL，所以說我們先讓 head 印出來它的數值，然後再把 current 設成 head 的下一個結點並印出數值，接著再把 current 設成 node2 的下一個結點並印出數值，直到 current 結點走到了 node3，在下一個結點沒有了，也就是 NULL，我們自然可以跳出迴圈
while(current != NULL) {
printf("%d ", current->data);
current = current->next;
}輸出結果
這裡我們可以看到輸出結果就是
5 128 41當然，畢竟我們的鏈結串列是動態宣告的，所以當成是結束後，我們也把取用來的記憶體一一的釋放掉
我們在這裡先宣告一個 previous 的 node
Node *previous = (Node*)malloc(sizeof(Node));再讓 current 等同於 head
current = head;我們讓每一個 current 進來的 node，都等同於 previous node，接著讓 current 成為下一個結點，而在每一次的循環當中，都會釋放掉 previous node，值得 current 等同於 NULL 跳出迴圈
while(current != NULL) {
previous = current;
current = current->next;
free(previous);
}寫成函數
現在我們把新增結點，印出結點以及釋放結點都寫成函數，這樣的話在應用以及維護程式碼方便將顯得更為方便
完整的程式碼
這裡我們先貼出完整的程式碼，隨後再一一拆解整個程式
新增節點的函數: add_node
我們在主程式中，先宣告了 head 的結構指標變數，隨後使用三個 add_node的函數來形成 5 -> 128 -> 41的鏈結串列
// create first node "head"
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);那麼我想很多看到這裡的讀者，都會疑問說為什麼我接收 Node 的參數是雙重指標的形式，也就是 Node **start，我會在下面的函數解說中一併解釋
首先進來這個函數後，我當然就動態宣告一個新的 Node 指標變數，並將值賦予它，注意，這時候下一個結點指向為 NULL
Node *new_node = (Node*)malloc(sizeof(Node));
new_node->data = value;
new_node->next = NULL;然後，第一次添加結點的時候，主程式如下
Node *head = NULL;
add_node(&head, 5);在這裡我來解釋我這邊使用 Node **start 的原因，因為如果我把它宣告為雙重指標的話，則我把 new_node 赴值給 *start 的指標變數的話，則就可以改變 head 的內容，也就是說，我使用這個方法第一次新增結點的話，我回到主程式去後，這個 head 變數，就成為了我第一次新增結點的那個指標結構變數。我知道對於指標不熟的讀者可能比較難以接受這個方法，不過事實上可以先使用的我的程式碼，編譯成功後再慢慢品味這樣的寫法，另外這樣的寫法其實也是我參照許多其他人對於鏈結串列的寫法後所採用的
然後這是我們第一次新增結點，所以 *start 為 NULL，我們把 new_node 賦給 *start，head 因此跟這個 new_node 所指向的地方是一樣的，如此我們就創立了第一個結點
if(*start == NULL) {
*start = new_node;
return;
}接著我們繼續新增結點下去，在主程式中，我們繼續新增了數值為 128 與41 的結點
int main(int argc, char* argv[])
{
// create first node "head"
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);print_list(head);
free_list(head);return 0;
}
同樣的，再回到 add_node，這時候 *start 已經不是 NULL 了，代表不是新增的第一個結點，所以是跑如下的程式碼，先讓 *start，也就是 head 的地方等同於 current node，然後不斷的檢查下一個 node 是不是指向 NULL，最後發現是指向 NULL 的那個結點，就代表著最後的那個結點，我們把新增的這個結點，放在目前走到的結點之後，current->next = new_node;，這樣就新增完成了。
else {
Node *current;
current = *start;
while(current->next != NULL) {
current = current->next;
}
current->next = new_node;
return;
}輸出結果
5 128 41遍歷整個鏈結串列: print_list
在主函數中，我們新增完結點後就可以印出來了
int main(int argc, char* argv[])
{
// create first node "head"
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);print_list(head);
free_list(head);return 0;
}
方法事實上也很簡單，我們傳進了 head 變數之後，使用一個迴圈，確認目前的結點是否為 NULL，不是的話印出目前的數值，是的話跳出迴圈然後印出一個換行符，這樣就可以遍歷印出了
void print_list(Node *node)
{
while(node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}釋放整個鏈結串列: free_list
在主函數中，最後一步就是釋放整個鏈結串列所佔的記憶體空間
int main(int argc, char* argv[])
{
// create first node "head"
Node *head = NULL;
add_node(&head, 5);
add_node(&head, 128);
add_node(&head, 41);print_list(head);
free_list(head);return 0;
}
這裡我們就先宣告一個 current 以及 temp 的結點，然後讓傳進來的 head 為 current，如果 current node 不等同於 NULL ，我們把 current node 賦值給 temp node ， current node 等同於目前的 current node 的下一個 node ，然後釋放掉 temp 的記憶體空間，如此就可以釋放掉整個鏈結串列
void free_list(Node *node)
{
Node *current, *temp;
current = node;
while(current != NULL) {
temp = current;
current = current->next;
free(temp);
}
}小結
鏈結串列是一個很基礎的資料結構，接觸較少的讀者可能會對建構鏈結串列過程的過多的指標感到不適應或一時難解，不過其實只要一個一個的解析，就可以理解到鏈結串列是如何建構的。
相關連結
