# Linked List 連結串列
[TOC]
## 介紹
Linked List (連結串列)是一種常見的資料結構，利用 **node 節點** 來記錄、表示、儲存資料，且利用每個 node 的 **pointer 指標** 來指向下一個 node，以此來連接多個 node，並以 **NULL** 來代表 Linked List 的終點。
```graphviz
digraph obj{
node[shape=record]
rankdir="LR"
A[label = "Node 1|{Data: 12|Pointer: 0x100104300}|Address: 0x1001042f0"]
B[label = "Node 2|{Data: 7|Pointer: NULL}|Address: 0x100104300"]
C[label=NULL]
A->B
B->C
}
```
## 程式碼
以下範例是自行設定 node 的數量以及每一個 node 內的 data 值。
```C=
#include <stdio.h>
#include <stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node Node;
int main(){
int i,val,num;
Node *first,*current,*previous;
printf("Number of nodes : ");
scanf("%d",&num);
for (i=0;i<num;i++){
current=(Node*)malloc(sizeof(Node)); /*建立新的node*/
printf("Data for node %d : ",i+1);
scanf("%d",&(current->data)); /*輸入node的data成員*/
if (i==0){ /*若此為第一個node*/
first=current; /*將指標first指向目前的節點*/
previous=current; /*將指標previous指向目前的節點*/
}
else{
previous->next=current; /*將前一個node的pointer指向目前的節點*/
current->next=NULL; /*將目前的pointer指向NULL*/
previous=current; /*將前一個node設為目前的node*/
}
}
current=first;
while(current!=NULL){
printf("address=%p,",current);
printf("data=%d,",current->data);
printf("next=%p,\n",current->next);
current=current->next;
}
return 0;
}
```
執行後可以得到以下結果:
:::success
Number of nodes : 3
Data for node 1 : 61
Data for node 2 : 85
Data for node 3 : 49
address=00000000000813C0,data=61,next=00000000000813E0,
address=00000000000813E0,data=85,next=0000000000081400,
address=0000000000081400,data=49,next=0000000000000000,
:::
* 程式解說 :
在此程式中，我們運用到了 **動態記憶體配置(malloc)** 有效的解決記憶體過多或過少的問題。在第12行的三個指向NODE型態的指標 first、current 與 previous 分別表示為指向串列的第一個節點、現在正要處理的點，以及前一個節點的指標。我們將三個 node 的 data 、 pointer 和位址都印出來，可以清楚知道前一個 node 的 pointer 指向下一個 node 的位址。
## 相關函式
### 列印函數 PrintList( )
輸入串列中第一個 node 的位址，並且利用 **走訪(traversal)** 的方式將串列中所有節點的 data 印出。
* **走訪(traversal)** : 即為沿著連結的方向，經過每一個 node。
```C=
void PrintList(Node* first){
Node* node=first; /*將node指向第一個節點*/
if (first==NULL){ /*如果串列是空的，則印出 List is empty!*/
printf("List is empty!\n");
}
else{ /*如果不是，則走訪並印出所有node的data值*/
while(node!=NULL){
printf("%d ",node->data);
node=node->next;
}
}
}
```
### 釋放記憶空間函數 FreeList( ) or ClearList( )
當串列不再使用時，需要回收由 malloc( ) 所佔去的記憶體空間。一樣利用 **走訪(traversal)** 的方式，輸入串列中第一個 node 的位址，依序將每個 node 的記憶空間釋放掉。
```C=
void FreeList(Node* first){
Node *current, *tmp;
current=first;
while(current!=NULL){
tmp=current;
currnet=current->next;
free(tmp);
}
}
```
### 搜尋函數 SearchNode( )
當我們要刪除或是插入 node 時，必須要先知道我們要找的位址在哪裡，因此藉由這個函數，我們可以輸入所要插入的串列位置以及所要找的data,透過 **走訪(traversal)** 的方式來找到第一筆符合此data的位址。
```C=
Node* SearchNode(Node* first, int item){
Node* node=first;
while(node->data!=NULL){
if (node->data==item){
return node;
}
else{
node=node->next;
}
}
return NULL; /*如果找不到符合的節點，則回傳NULL*/
}
```
### 插入節點函數 InsertNode( )
在找到要插入地位址之後，便可以將所要插入的 node 資料放進去。InsertNode函數接收兩個引數，節點的位址以及所要輸入的 data。
```C=
void InsertNode(Node* node, int item){
Node* newnode=(Node*)malloc(sizeof(Node));
newnode->data=item;
newnode->next=node->next;
node->next=newnode;
}
```
另外，為了方便操作，以下再介紹兩個函式 **Push_front( )** 以及 **Push_back( )** ,
分別是在串列的**第一個前**以及**最後一個之後**再插入新的資料。
* #### Push_front( )
```C=
void Push_front(int a){
Node* newnode=(Node*)malloc(sizeof(Node));/*建立新的node*/
newnode->data=a; /*輸入node的data值*/
newnode->next=first; /*將新的node的pointer指向first*/
first=newnode; /*將first換到新的node的位置*/
}
```
* #### Push_back( )
```C=
void Push_back(int a){
Node* newnode=(Node*)malloc(sizeof(Node));/*建立新的node*/
newnode->data=a;
newnode->next=NULL;
if (first==0){ /*如果list是空的，令newnode為first*/
first=newnode;
}
else{
Node* current=first;
while (current->next!=NULL){ /*尋找最後一個node的位置*/
current=current->next;
}
current->next=newnode; /*將newnode接上尾巴的位置*/
}
}
```
### 刪除節點函式
輸入串列的位址以及所想要刪除的 node 的位址，經過刪除後，可以得到新的串列的位址。當我們要刪除的時候，記得要作釋放記憶體的動作!!
```C=
Node* DeleteNode(Node* first, Node* node){
Node* ptr=first;
if (first==NULL){ /*當串列是空的時候，印出Nothing to delete!*/
printf("Nothing to delete!\n");
return NULL;
}
if(node==first){ /*當第一個是要刪除的node時*/
first=first->next; /*將first更改為下一個節點的位址*/
free(node); /*釋放記憶體*/
return first;
}
else{
while(ptr->next!=node){ /*尋找所要刪除的node的位址*/
ptr=ptr->next;
}
ptr->next=node->next; /*將前一個node的pinter指向下一個node*/
free(node); /*釋放記憶體*/
return first;
}
}
```
### 反轉串列函式 Reverse( )
將串列的順序整個顛倒過來。
```graphviz
digraph obj{
node[shape=record]
rankdir="LR"
A[label = "A|Data: 12"]
B[label = "B|Data: 7"]
C[label = "C|Data: 53"]
N[label=NULL]
A->B
B->C
C->N
}
```
將第一個 node(A) 的 Pointer 指向 NULL，再將後面一個 node(B) 指向自己。
```graphviz
digraph obj{
node[shape=record]
rankdir="LR"
A[label = "A|Data: 12"]
B[label = "B|Data: 7"]
C[label = "C|Data: 53"]
N1[label=NULL]
N2[label=NULL]
A->B[style=dashed]
B->C
C->N1
N2->A[dir="back",arrowhead="normal",arrowtail="normal"]
}
```
不過此時原本B的位址只有A知道，經過這個步驟後，B的位址就找不到了。因此我們會需要多一個指標來記錄下一個 node 的位址。最後即可得到以下串列
```graphviz
digraph obj{
node[shape=record]
rankdir="LR"
A[label = "A|Data: 12"]
B[label = "B|Data: 7"]
C[label = "C|Data: 53"]
N1[label=NULL]
N2[label=NULL]
A->B[dir="back",arrowhead="normal",arrowtail="normal"]
B->C[dir="back",arrowhead="normal",arrowtail="normal"]
C->N1[style=dashed]
N2->A[dir="back",arrowhead="normal",arrowtail="normal"]
}
```
```C=
void Reverse(){
if (first==0||first->next==0){
return ;
}
Node *previous, *current, *preceding ;
previous=NULL;
current=first;
preceding=first->next;
while (preceding!=NULL){
current->next=previous;
previous=current;
current=preceding;
preceding=preceding->next;
}
current->next=previous;
first=current;
}
```
### 範例
最後我們將以上的所有函式套入以下的範例。其中我們先將串列的 data 設定好，再套用函式進去
```C=
#include <stdio.h>
#include <stdlib.h>
struct node{ /*建立structure*/
int data;
struct node *next;
};
typedef struct node Node;
Node *current, *first, *previous;
void InsertNode(Node* node, int item){ /*插入node*/
Node* newnode=(Node*)malloc(sizeof(Node));
newnode->data=item;
newnode->next=node->next;
node->next=newnode;
}
void PrintList(Node* first){ /*印出串列*/
Node* node=first;
if (first==NULL){
printf("List is empty!\n");
}
else{
while(node!=NULL){
printf("%d ",node->data);
node=node->next;
}
printf("\n");
}
}
Node* SearchNode(Node* first, int item){ /*搜尋節點位址*/
Node* node=first;
while(node->data!=NULL){
if (node->data==item){
return node;
}
else{
node=node->next;
}
}
return NULL;
}
void Push_front(int a){ /*插入新node在前面*/
Node* newnode=(Node*)malloc(sizeof(Node));
newnode->data=a;
newnode->next=first;
first=newnode;
}
void Push_back(int a){ /*插入新node在尾巴*/
Node* newnode=(Node*)malloc(sizeof(Node));
newnode->data=a;
newnode->next=NULL;
if (first==0){
first=newnode;
}
else{
Node* current=first;
while (current->next!=NULL){
current=current->next;
}
current->next=newnode;
}
}
void FreeList(Node* first){ /*釋放記憶空間*/
Node *current, *tmp;
current=first;
while(current!=NULL){
tmp=current;
current=current->next;
free(tmp);
}
}
Node* DeleteNode(Node* first, Node* node){ /*刪除節點*/
Node* ptr=first;
if (first==NULL){
printf("Nothing to delete!\n");
return NULL;
}
if(node==first){
first=first->next;
free(node);
return first;
}
else{
while(ptr->next!=node){
ptr=ptr->next;
}
ptr->next=node->next;
free(node);
return first;
}
}
void Reverse(){ /*反轉串列*/
if (first==0||first->next==0){
return ;
}
Node *previous, *current, *preceding ;
previous=NULL;
current=first;
preceding=first->next;
while (preceding!=NULL){
current->next=previous;
previous=current;
current=preceding;
preceding=preceding->next;
}
current->next=previous;
first=current;
}
int main(){
int num[5]={9,54,61,5,27}; /*設定串列的個數及data*/
int i;
for (i=0;i<5;i++){
current=(Node*)malloc(sizeof(Node));
if (i==0){
first = current;
}
else{
previous->next=current;
}
current->data=num[i];
current->next=NULL;
previous=current;
}
current=first;
PrintList(first);
Push_front(38); /*分別在串列前後插入新節點38,65*/
Push_back(65);
printf("After Push_front() and Push_back():\n");
PrintList(first);
Node* node1=SearchNode(first,61); /*搜尋61所在的node位址，並插入新節點46*/
InsertNode(node1,46);
printf("After SearchNode() and InsertNode():\n");
PrintList(first);
Reverse(); /*反轉整個串列*/
printf("After Reverse():\n");
PrintList(first);
Node* node2=SearchNode(first,54); /*搜尋並刪除54所在的node位址*/
DeleteNode(first,node2);
printf("After SearchNode() and DeleteNode():\n");
PrintList(first);
FreeList(first); /*釋放記憶體*/
return 0;
}
```
執行後可以得到以下結果 :
:::success
9 54 61 5 27
After Push_front() and Push_back():
38 9 54 61 5 27 65
After SearchNode() and InsertNode():
38 9 54 61 46 5 27 65
After Reverse():
65 27 5 46 61 54 9 38
After SearchNode() and DeleteNode():
65 27 5 46 61 9 38
:::