# Linked List
Array 是使用程式時，一種非常方便的儲存格式，可以儲存資料也可以處理字串。但是使用 Array 時有一個最大的問題，程式一開始就要分配給 Array 一個空間，這個空間多大或是多小是由我們來決定。
當宣告的空間太大時，程式會佔用多餘的記憶體空間，當宣告的空間太小時，儲存或存取的資料超過 Array 的儲存空間時，這個 Array 就會發生存取資料錯誤的問題。
有沒有一種儲存資料的格式可以讓我們依照自己的需求，在程式運行的過程中依據程式執行的狀況添加資料到這種儲存格式，我們不用擔心分配的儲存空間不夠或是浪費了沒有使用到的儲存空間？
在 C 語言中提供了一種資料型態叫做 Struct，這個功能可以讓我們把不同的資料類型打包起來放在一起作為一個新的類別，透過這個類別可以取用這個類別中不同資料型態的資料。
C 語言中也提供了一種連結資料的方式稱作 Pointer，可以讓我們透過記憶體位址找到這一個資料。使用 Array 時我們可以知道下一筆資料放在哪邊是因為他們的資料被連續分配再一起，我們建立一個 Struct 裡面分別存放著**資料**與他下一筆資料的**位址**，是不是可以達成 Array 的功能，這種資料型別稱作 Linked List(鏈結串列)。
## Singly Linked List
鏈結(Linking)的方向只有一個。
實作方式:使用一個 Struct(Node) 包含 data 跟 link 來建置這種資料結構。
```c=
struct node{
int data;
struct node *link;
}
```
### Array 與 Singly Linked List 的差異
範例: 輸入數字進行相加的使用例子
Array
宣告一個陣列，接著我們將輸入的資料一筆一筆的放到陣列中，放完後在從陣列中一筆一筆地進行相加。
```c=9
for(int i = 0; i < num; i++){
scanf(" %d ", &number[i]);
}
for(int i = 0; i < num; i++){
sum += number[i];
}
```
<!--[Source code](https://ideone.com/nIRDTN)-->
Singly Linked List
使用 linkedlist 時，資料跟資料之間無法像 array 一樣，資料連結再一起。使用這種資料結構必須先產生一種資料類型，使他可以知道下一個資料的位址。
```c=4
struct node{
int data;
struct node *link;
};
```
宣告一個陣列，接著我們將輸入的資料一筆一筆的放到陣列中，放完後在從陣列中一筆一筆地進行相加。
```c=16
for(int i = 0; i < num; i++){
if(i == 0){
numbers = (struct node*)malloc(sizeof(struct node));
scanf(" %d ", &numbers->data);
numbers->link = NULL;
start = numbers; //struct node *
}else{
numbers->link = (struct node*)malloc(sizeof(struct node));
numbers = numbers->link;
scanf(" %d ", &numbers->data);
numbers->link = NULL;
}
}
numbers = start; //struct node *
for(int i = 0; i < num; i++){
if(numbers != NULL){
sum += numbers->data;
if(i)printf(" + ");
printf("%d", numbers->data);
numbers = numbers->link;
}
}
```
**Notice: 1. 使用 malloc 動態分配記憶體空間時需要宣告 stdlib.h 標頭檔。 2. 不能在 while 中在建立 struct 的指標，否則程式在運行時編譯器發生問題。**
<!--[Source code](https://ideone.com/0kxKBT)-->
### Linked List 常見的幾個操作
Length
Concatenate
Invert
### 實作 Singly Linked List 基本的操作
LinkedList length
```c=
int LinklistLength(struct node *start){
int length = 0;
struct node *list = start;
while(list != NULL){
length ++;
list = list->link;
}
return length;
}
```
Add Node
找到 Singly Linked List 的最後一個 node ，將新增的資料放在這個 node 後面。
```c=
void addNode(struct node *start, int Idata){
struct node *list = start;
while(list != NULL){
if(list->link == NULL){
list->link = (struct node *)
malloc(sizeof(struct node));
list = list->link;
list->data = Idata;
list->link = NULL;
}
list = list->link;
}
}
```
Delete Node
依照書上的內容，將當前 linkedlist(start) 的記憶體位址先記錄在 temp 中，並將 start 的記憶體位址下一個 node 位址，接著將 temp 紀錄的 linkedlist 第一個 node 的位址清空還給電腦。
```c=
void deleteNode(struct node *start){
struct node *temp = start;
start = start->link;
free(temp);
}
```
只是這種作法會造成程式的 linkedlist 發生問題，釋放的 temp 記憶體位址同時把存放在 main 中 linkedlist 的記憶體位址並沒有被改變，釋放這個記憶體位址時會讓 main 傳入的 linkedlist 的記憶體位址也被釋放歸還給電腦，造成 linkedlist 發生錯誤。
version 1
```c=
struct node *deleteNode(struct node *start){
struct node *temp;
temp = start;
start = start->link;
free(temp);
return start;
}
```
main 中也要用指標來接收回傳的記憶體位址。
```c=
<linklist_name> = deleteNode(<linklist_name>);
```
version 2
```c=
void deleteNode(struct node *start){
struct node *list;
list = start->link;
*start = *start->link;
free(list);
}
```
version 3
```c=
void deleteNode(struct node **start){
struct node *temp;
temp = *start;
*start = (*start)->link;
free(temp);
}
```
在 main() 中對應的程式碼也要修改為傳入記憶體位址。在 function 引入的內容變成傳入 linkedlist 的記憶體位址，讓 function 達成在副程式直接修改記憶體位址，當 function 將對應的記憶體位址釋放後，不會發生指標位址與當前 start 指向的記憶體位址不一致的問題，造成在 function 釋放記憶體位址後影響到原本 main 的 linkedlist 的記憶體位址也被程式釋放，進一步造成原本 main 的 linkedlist 內容發生錯誤。
```c=
deleteNode(&<linklist_name>);
```
<!--[Source code](https://ideone.com/R5Owt1)-->
Insert Node
Delete Linked List
Concatenate Linked List
將兩個 Linkedlist 連結在一起。
[Source code](https://ideone.com/8Wxhhs)
Inverse Linked List
改變 Linkedlist 的 linking 方向。
需要使用三個指標來達成這個功能。完成後，要回傳最後一個 Linkedlist node 的 address。
<!--[Source code](https://ideone.com/4GE7qi)-->
## Circular Linked List
在 Singly Linked List 中，將最後一個 node 的鏈結(link)指向第一個 node。
不論從哪一個 node 開始，都可以拜訪所有 node。
回收整條 linked list 的 time O(1)
連結(concatenate)兩條 circular linked list 變成一條 circulat linked list 的 time 為 O(1)
## Doubly Linked List
Linking 具有兩個方向，可以前往上一個 node 或下一個 node。
實作方式:一個 Node(Struct) 中包含 LLink 、 Data 、 RLink 這三個資料型別來儲存資料，LLink 與 RLink 分別為 pointer 用來紀錄前(左)與後(右)一個 node 的記憶體位址。
```c=
struct node{
int data;
struct node *Llink, *Rlink;
}
```
## Stack
Node Struct: Data Link
Stack Struct: Top
action: push(s, item), pop(s)
## Queue
Singly linkedlist
Node Struct: Data Link
Linkedlist Struct: rear, front
action: Enqueue(Q, item), Dequeue(Q)
Circular linklist
Linklist Struct: rear
## Other
判斷 Linked list 是否有 Circular linked list 狀況的問題
=> 龜兔賽跑演算法[Floyd's Algorithm](http://web.ntnu.edu.tw/~algo/Function.html)
## Comparison
### Linked list
各個 Node 不一定佔用連續的記憶體空間，可以為非連續的記憶體空間。
各個 Node 的 type 不一定要相同，只支援 Sequential Access，不支援 Random Access。
循序存取速度慢(要先 read link info. 才能知道下一個 node 的位址)
可靠度差(link 斷掉了，串列就分開了)
可以動態地增、刪 node 的空間，Insert、Delete list 元素容易(只需改變 pointer 就好)
Time:O(1)
### Array
佔用連續的記憶體空間
各個元素的型態皆必須相同，Array 支持 Random Access 及 Sequential Access。
循序存取速度較快
可靠度佳(可以預測存在 Array 中的資料位址)
使用 Array 之前必須先宣告大小，無法動態地增刪分配的空間，Insert、Delete array 元素麻煩(必須先移動其他元素)
Time:O(n)
###### tags: `DS`
Sign in with Wallet
Connect another wallet