# Chap. 04 - Linked List
> 課程內容 : 中興大學應用數學系 顏增昌教授 (111 學年度第 1 學期)
> 參考書目 : Fundamentals of Data Structures in C (2nd), Ellis H., Sartaj S., Susan A.-F.
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
## Content
* [Sec. 4.1 Singly linked lists](#Sec41-Singly-linked-lists)
* [1. Sequential representation](#1-Sequential-representation)
* [2. Linked representation](#2-Linked-representation)
* [2.1 Insertion](#21-Insertion)
* [2.2 Deletion](#22-Deletion)
* [Sec. 4-2 Linked list with singe node](#Sec-4-2-Linked-list-with-singe-node)
* [1. Review of C](#1-Review-of-C)
* [1.1 Structure](#11-Structure)
* [1.2 Typedef](#12-Typedef)
* [1.3 Self-referenttial structures](#13-Self-referenttial-structures)
* [2. Use C to represent link](#2-Use-C-to-represent-link)
* [2.1 Create a single node linked list](#21-Create-a-single-node-linked-list)
* [2.2 Insertion and deletion](#22-Insertion-and-deletion)
* [3. Basic implement](#3-Basic-implement)
* [Sec. 4.3 Linked stacks and queues](#Sec-43-Linked-stacks-and-queues)
* [1. Linked stacks](#1-Linked-stacks)
* [1.1 Definition](#11-Definition)
* [1.2 Push](#12-Push)
* [1.3 Pop](#13-Pop)
* [1.4 Linked stack implement](#14-Linked-stack-implement)
* [2. Linked queues](#2-Linked-queues)
* [2.1 Definition](#21-Definition)
* [2.2 Add](#22-Add)
* [2.3 Delete](#23-Delete)
* [2.4 Linked queue implement](#24-Linked-queue-implement)
* [Sec. 4.4 Circular list](#Sec-44-Circular-list)
* [1. Representation of circular list](#1-Representation-of-circular-list)
* [2. Get and return node](#2-Get-and-return-node)
* [3. Delete circular list](#3-Delete-circular-list)
* [Sec. 4.5 Others operation of list](#Sec-45-Others-operation-of-list)
* [1. Invert](#1-Invert)
* [1.1 Implement of invert](#11-Implement-of-invert)
* [2. Concatenate](#2-Concatenate)
* [2.1 Implement of concatenate](#21-Implement-of-concatenate)
* [3. Operation of circular list](#3-Operation-of-circular-list)
* [3.1 Insert](#31-Insert)
* [3.2 Length](#32-Length)
* [3.3 Implement of circular lis](#33-Implement-of-circular-list)
* [Sec. 4.6 Doubly linked list](#Sec-46-Doubly-linked-list)
* [1. Insert](#1-Insert)
* [2. Delete](#2-Delete)
## Sec. 4.1 Singly linked lists
### 1. Sequential representation
前面章節介紹的 stack 與 queue 等資料結構，都是以 array 來實作的有序串列表示法。Array 的特點是將==相同資料型態==儲存在一段==連續==的記憶體之中，這種性質會導致以下這些問題 :
* 進行插入(insertion)與刪除(deletion)時會需要進行**資料的搬移(data movement)**
* 當需要在序列中的任意位置進行插入/刪除時，需要付出極大的成本
* 當儲存的資料大小不同時，會耗費記憶體空間
* 當資料長度不確定時，需要事先宣告一個大的 array，造成**空間的浪費**
假設一個有序串列為 S = ["bat", "cat", "sat", "vat"]，當需要新增 "fat" 字串時，需要先把 "sat" 與 "vat" 往後移動再插入 "fat"。
### 2. Linked representation
為了改善有序串列的表示方式，可以使用 linked list 的表示法。Linked list 表示法的優點在於可以將資料放在記憶體中的==任意位址==。
在有序表示法中，元素的的順序(order of elements)和有序串列(ordered list)是一樣的，但在 linked representation 中元素順序與串列順序不會一樣，因此每個元素除了儲存資料以外，還必須**儲存下一個元素的位址。***
Linked representation 中的每個元素稱為節點(node)，每個節點包含兩個兩個部分 :
* 資料(data components)
* 指標(pointer)/鏈結(link)，用來指向下一個節點的位址
如上圖所示，array 是以一段==連續==的記憶體空間來儲存資料，linked list 中資料不需要放在連續的位址，並新增一個陣列 link 來儲存資料的指標，對任一筆資料 i 而言，data[i] 儲存資料，link[i] 儲存指標，兩者合併為一個節點。
第一筆資料的位址是 6，所以用一個變數 `first = 6` 儲存第一筆資料 data[0] = "Bat" 的位址，link[0] = 3 指向下一筆資料 data[1] = "Cat" 的位址，依此推類。最後的資料 data[3] = "Vat" 因為沒有下一筆資料，所以 link[3] = 0。
Linked list 的圖示表示法，通常會用一串照順序排列的節點以及以箭頭表示的鏈結(link)，最後一個節點的指標會指向 `NULL` 並以接地符號表示，如下圖所示，稱為單項鏈結串列(singly linked list)。在 singly linked list 中，每個節點只有一個指標，link 是由零個或多個節點所組成，當節點數為 0 時表示 link 是空的。
#### 2.1 Insertion
Linked list 的優勢在於可以用簡單的步驟來進行==對任意位置插入節點==，以下圖為例，要在一個 linked list 中插入 "mat" 字串 :
* 產生一個新的節點(data+link)並用指標 paddr 指向這個新的節點
* 將字串 "mat" 寫入到 data field
* 將 paddr 的 link field 指向下一個節點(sat)的位址
* 前一個節點(cat)的 line field 指向新的節點 paddr
#### 2.2 Deletion
Linked list 刪除特定位址的節點時，也==不用作任何的資料搬移==，以下圖為例，要刪除 linked list 中的 "sat" 字串 :
* 找到欲刪除節點的前一個節點(cat)
* 將前一個節點(cat)的 link field 指向後一個節點(vat)
## Sec. 4-2 Linked list with singe node
### 1. Review of C
#### 1.1 Structure
結構(structure)型態是 C 語言中的一種資料型態，用來包含其他不同型態的一種資料型態。如以下程式碼中，定義了一個名為 data 的結構型態，其中包含了字元陣列以及整數型態兩種欄位。
```c
struct data{
char name[10];
int math;
}
```
結構型態的變數有兩種宣告方式
1. 先定義再宣告
2. 定義宣告一次完成
```c
/* first declaration method */
struct data{
char name[10];
int math;
}
struct data student_1; /* 宣告 data 結構的變數*/
/* second declaration method */
struct data{
char name[10];
int math;
}studen_1;
```
#### 1.2 Typedef
在 C 語言中可以使用關鍵字 `typedef` 來定義某個資料型態為其他識別字，如 `trpedef int INT;` 就是將整數型態 `int` 以 `INT` 來表示。搭配結構型態(structure type)使用的話可以將結構型態定義為其他關鍵字。`typedef` 搭配 `struct` 同樣有兩種定義方式
* 先定義結構，再定義識別字
* 結構與識別字同時定義
```c
/*first definition */
struct data{
char name[10];
int math;
}
typedef struct data SCORE; /* 將 data 結構定義為 SCORE */
/* second definition */
typedef struct{
char name[10];
int math;
} SCORE; /* 直接定義結構為新的識別字 SCORE */
```
#### 1.3 Self-referenttial structures
在 C 語言中還有一種自我參考結構(self-referential structures)的結構型型態，它也是一個結構，但內部的欄位有一個指向自己的指標。
```c
typedef struct list{
char name[10];
list *link; /* 指向自己的指標 */
};
```
在 C 語言中對這種自我參考結構有一個特例，可以允許程式先建立一個尚未存在型態的指標，之後再定義這個結構型態。以下面的程式碼片段為例 :
* 聲明一個名為 data 的結構體 `struct data` (此聲明不一定要)
* 聲明完後可建立一個指向 data 結構的型態 `dataPointer`，此型態表示指向 data 結構的指標
* 此時 data 結構的內容尚未定義
* `dataPointer` 是一個自定義的資料型態，它表示一個指向 data 結構的指標，實際上就等價於 `struct data *`
* 最後再定義 data 結構的內容，內部包含一個指向自己的指標 ptr
```c
struct data; /* declaration a struct type named data */
typedef struct data *dataPointer; /* construct a pointer to point struct data */
struct data{
char name[10];
dataPointer ptr ;
}
```
### 2. Use C to represent link
藉由上述 C 語言的自我參考結構與特殊的定義宣告方式，可以宣告一個節點結構如下，`listPointer` 是一個自定義的資料型態，用來表示指向 listNode 結構的指標
```c
typedef struct listNode listNode /* 這行不一定要 */
typedef struct listNode *listPointer;
struct listNode {
int data;
listPointer link;
};
```
#### 2.1 Create a single node linked list
有了上述的定義與宣告方式後，透過宣告 `listPointer first = NULL` 可以宣告一個空的串列，因為 first 本身是一個指向 listNode 的指標，初始值設為 `NULL` 表示第一個節點的位址是空的，意即沒有任何節點存在。以圖示表示的話代表直接接地，如下圖所示。
產生節點的方式可以使用 `malloc()` 等函式來動態分配一段記憶體，且記憶體大小空間為 `sizeod(*first)`。因為 `first` 變數的資料型態是指向 listNode 結構的指標，所以當使用 `*` 運算子時表示取出 `first` 指標所指向的內容，也就是 listNode 結構，因此 `sizeof(*first)` 代表的是 lintNode 結構的大小。當然，也可直接使用 `sizeof(listNode)` 來計算 linstNode 結構的大小。
創建完節點後再對該節點的 data field 與 link field 賦值。因為是單一節點，所以節點後沒有其他節點，link field 直接設為 `NULL` 表示接地。單一節點的 linked list 的示意圖如下圖。
> The following code is saved in `single_node.c`.
```c=
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(void){
listPointer first = NULL; /* create a linked list whose name is first */
MALLOC(first, sizeof(*first)); /* create a node */
first->data = 50; /* assign data */
first->link = NULL; /* assign link */
printf("The data in first node: %d\n", first->data);
printf("The link in first node: %p\n", first->link);
free(first);
return 0;
}
```
#### 2.2 Insertion and deletion
##### 先定義一個可創建具有兩個節點的 linked list 的函式
> The following code is saved in `LinkListADT.c`
```c=
/* LinkedListADT.c */
listPointer Create2Node(){
/* create and initialize a linkedlist with 2 nodes */
listPointer first, second;
MALLOC(first, sizeof(listNode));
MALLOC(second, sizeof(listNode));
first -> data = 10;
first -> link = second;
second -> data = 20;
second -> link = NULL;
return first;
}
```
##### 插入節點的過程示意圖如下所示
> The following code is saved in `LinkedListADT.c`
```c=
/* LinkedListADT.c */
void insert(listPointer *ptr, listPointer node){
/* Insert a new node with data = 50 into the list after node */
listPointer temp;
MALLOC(temp, sizeof(listNode));
temp -> data = 50;
if (*ptr){
temp -> link = node -> link;
node -> link = temp;
}
else{
temp -> link = NULL;
*ptr = temp;
}
}
```
進行節點的插入時要注意以下事項 :
* 參數 `listPointer *ptr` 代表指向指標的指標，用來傳入指向第一個節點的指標的位址(即 `&first`)
* 參數 `listPointer node` 代表要插入的位置的前一個節點
* 插入時分兩種情況討論
* 如果第一個節點非空(`*ptr != NULL`)，則把舊的 link 放到新的 link 中，再把新的位址放入到舊的 link 中(先接後再接前)
* 如果第一個節點為空(`*ptr == NULL`)，則插入的就是第一個節點，link 直接設為 `NULL` 並更新 ptr 指向的位址
:::info
**參數為何要使用指向指標的指標(`listPointer *ptr`)而不是直接使用指標(`listPointer ptr`) ?**
當傳遞指標時，函數內部是==傳遞指標的副本==，對指標所指向的位址有改變的話不會傳遞到外面。只有對這個指標使用 `*` 運算後，指標所指向位址的內容的改變才會傳遞到函數外部。
如果需要改變指標指向的位址，需要傳遞指向這個指標的指標，再透過 `*` 運算來修改第一個指標的位址，使他指向別的資料。(參見下圖)
:::
##### 刪除節點的過程示意圖如下所示
> The following code is saved in `LinkedListADT.c`.
```c=
/* LinkedListADT.c */
void delete(listPointer *ptr, listPointer trail, listPointer node){
/** Delete the node from the list.
* trail is the preceding node.
* ptr is the head of the list.
*/
if (trail){ /* the deleted node is NOT head */
trail -> link = node -> link;
}
else{ /* the deleted node is head*/
*ptr = node -> link;
}
free(node);
}
```
進行節點的刪除時要注意以下事項 :
* 參數解釋
* `*ptr` : 指向 listPointer 的指標(指向指標的指標)，如同插入時的參數
* `trail` : 要刪除節點的前一個節點
* `node` : 要刪除的節點
* 插入時分兩種情況討論
* 如果要刪除的不是第一個節點，則 `trail != NULL;`，會把要刪除的 node 指向的下一個節點往前接上前一個節點 `trail`
* 如果要刪除的是第一節點，則 `trail == NULL;`，第一個節點的位址(`*ptr`)會改為要刪除的 node 指向的下一個節點
##### 印出節點資料
> The following code is saved in `LinkedListADT.c`.
```c=
/* LinkedListADT.c */
void print_list(listPointer ptr){
for (; ptr; ptr = ptr -> link){
printf("data = %d\n", ptr->data);
}
}
```
每印出一個節點的資料後，就把該節點的 link 指向的下一個節點的位址往前移動給 `ptr`，直到打印出最後一個節點後 `ptr == NULL;` 迴圈停止。
這裡的參數不使用指向指標的指標(`listPointer *ptr`)的原因是因為，只需要在函數內部修改所指向的位址就行，這個修改不用傳遞到函數外部，因為函數外整個 list 的結構沒有發生改變，所以傳遞第一個節點的位址(`listPointer ptr`)就好。
##### 釋放節點所佔的記憶體空間
> The following code is saved in `LinkedList.c`.
```c=
/* LinkedList.c */
void freeList(listPointer ptr){
listPointer temp;
while (ptr){
temp = ptr; /* save current head node */
ptr = ptr -> link; /* move the head node to second */
free(temp);
}
}
```
### 3. Basic implement
> The following code is saved in `insertion_deletion.c`.
```c=
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(void){
listPointer first;
/* create linked list with 2 nodes */
printf("Create linked list:\n");
first = Create2Node();
printList(first); /* 10 -> 20 -> NULL */
/* insert a node after second node */
printf("Insert a node:\n");
insert(&first, first->link);
printList(first); /* 10 -> 20 -> 50 -> NULL */
/* delete the frst node */
printf("Delete a node:\n");
delete(&first, NULL, first);
printList(first); /* 20 -> 50 -> NULL */
freeList(first);
return 0;
}
```
## Sec. 4.3 Linked stacks and queues
前一章節介紹的 stack 與 queue 都是只有實作單一的一個 stack 或 queue，當有多個 stacks 或 queues 同時存在時，可以使用 linked 的概念將多個 stacks 或 queue 使用 sequence 的方式串聯起來。
如上圖所示，每個 top[i] 的位置都儲存了一個 stack，且 top[i] 指向 stack 的頂端元素。以此方式可以將多個 stack 使用 sequence 的方式組合起來，並輕鬆的進行 push 與 pop。
### 1. Linked stacks
#### 1.1 Definition
綜合 stack 與 linked list 兩者的定義與宣告，必須先
1. 定義一個 stack 中元素的結構
2. 自訂一個指向 `struct stack` 型態的指標 `*stackPointer`
3. 定義自我參考結構 `struct stack`
```c=
#define MAX_STACK_SIZE 3
typedef struct {
int key;
} element;
typedef struct stack *stackPointer;
struct stack{
element item;
stackPointer link;
};
```
有了上述定義後，就可以透過 `top[MAX_STACK_SIZE]` 宣告一個具有三個 stacks 的 linked stacks。
#### 1.2 Push
如圖 stack 的新增元素一樣是在每個 stack 的頂端新增元素，stack 頂端指的是每層 top[i] 指向的位址。
需注意的是，在每個 linked stack 新增元素時順序跟 linked list 一樣，必須先接後面節點，再接前面節點。
> The following code is saved in `LinkedStackQueue.c`.
```c=
/* LinkedStackQueue.c */
void push(stackPointer *top, int i, element item){
stackPointer temp;
MALLOC(temp, sizeof(*temp));
temp -> item = item;
temp -> link = *(top + i); /* 先接後 */
*(top + i) = temp; /* 再接前 */
}
```
#### 1.3 Pop
在刪除元素時與 stack 一樣刪除後會回傳刪除後的元素。需要注意的是在刪除時需要先用一個變數(`temp`)將欲刪除的元素儲存，才能連接後面的節點，否則欲刪除的元素一旦斷掉就找不回來，會浪費記憶體空間。
> The following code is saved in `LinkedStackQueue.c`.
```c=
/* LinkedStackQueue.c */
element pop(stackPointer *top, int i){
element item;
stackPointer temp;
temp = (*(top + i));
item = temp -> item;
(*(top + i)) = temp ->link;
free(temp);
return item;
}
/* print the all linked stack */
void printLinkedStack(stackPointer *top, int i){
stackPointer temp = *(top+i);
printf("top[%d] = ", i);
for (; temp; temp=temp -> link){
printf("%d ", temp->item);
}
printf("\n");
}
```
#### 1.4 Linked stack implement
> The following code is saved in `linked_stack.c`.
```c=
/* linked_stack.c */
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(void){
stackPointer top[MAX_STACK_SIZE];
element a = {10}, b = {20}, c = {30}, d = {40};
int i;
/* initialize linked stack */
for (i=0; i<MAX_STACK_SIZE; i++)
top[i] = NULL;
/* push */
push(top, 0, a);
push(top, 1, b);
push(top, 2, c);
push(top, 1, d);
printLinkedStack(top, 0); /* top[0] = 10 */
printLinkedStack(top, 1); /* top[1] = 40 20 */
printLinkedStack(top, 2); /* top[2] = 30 */
/* pop */
pop(top, 1);
printLinkedStack(top, 0); /* top[0] = 10 */
printLinkedStack(top, 1); /* top[0] = 20 */
printLinkedStack(top, 2); /* top[0] = 30 */
return 0;
}
```
### 2. Linked queues
使用 linked 的方式多個 queue 的概念與 linked stack 基本類似，同樣是用 array 來儲存多個不同的 queue。但因為 queue 不像 stack 一樣是從單側的 top 端進行插入與刪除，queue 是從 rear 端新增與 front 端刪除，所以需要有 2 個 array 來指向 front 與 rear，如下圖所示
#### 2.1 Definition
同樣參考 linked 與 queue 的定義與宣告方式，製作 linked queue 時需要 :
1. 定義 queue 中元素的結構(同 stack)
2. 自訂一個指向 `struct queue` 型態的指標 `*queuePoint`
3. 定義自我參考結構 `struct point`
```c=
#define MAX_QUEUE_SIZE 3
typedef struct queuePoint *queuePoint;
struct queuePoint{
element item;
queuePoint link;
};
```
有了上述定義後，可以透過 `front[MAX_QUEUE_SIZE` 與 `rear[MAX_QUEUE_SIZE]` 宣告一個有三個 queues 的 linked queue。
#### 2.2 Add
刪除某個 queue 的節點時，需先檢查該 queue 是不是空的，如果不是就可以直接從 rear 端新增，反之如果是空的，則 front 端與 rear 端都要指向新的節點，如下圖所示。
> The following code is saved in `LinkedStackQueue.c` .
```c=
/* LinkedStackQueue.c */
void addq(queuePoint *front, queuePoint *rear, int i, element item){
/* create a node */
queuePoint temp;
MALLOC(temp, sizeof(struct queuePoint));
temp -> item = item;
temp -> link = NULL;
if (front[i]){ /* front not NULL */
rear[i] -> link = temp;
rear[i] = temp;
}
else { /* front is NULL and temp is first and lat */
front[i] = temp;
rear[i] = temp;
}
}
```
與 linked stack 不同的是函數內部這次是直接使用 `front[i]` 來找 array 的內容，不是用 `*(front+i)`
#### 2.3 Delete
刪除某個 queue 的節點時，同樣要檢查是不是空的。如果不是空的才可以刪除。刪除時切記要先把欲刪除的節點複製一份，避免刪除後找不到該節點，無法釋放記憶體空間。
此外，刪除的步驟與一般的 queue 類似，記得要先取值，再斷開(刪除)鏈結，如下圖所示。
> The following code is saved in `LinkedStackQueue.c`.
```c=
/* LinkedStackQueue.c */
element deleteq(queuePoint *front, int i){
queuePoint temp = front[i];
element item, EMPTY = {0};
if (!temp){
printf("The queue is EMPTY.\n");
return EMPTY;
}
item = temp->item; /* get data */
front[i] = temp -> link; /* delete temp */
free(temp);
return item;
}
/* print the all linked queue */
void printLinkedQueue(queuePoint *front, int i){
queuePoint temp = *(front + i);
printf("Front[%d] = ", i);
for (; temp; temp = temp -> link){
printf("%d ",temp->item.key);
}
printf("= Rear[%d]\n", i);
}
```
:::info
打印節點時，因為 queuePoint 內部結構是使用 `element` 當作 data field，所以打印時理論上要使用 `temp -> item.key`。前面的 linked stack 沒有使用也可以打印的原因似乎是因為編譯器會自動將 element 結構中的第一個值(即 key)作為結果輸出。
:::
#### 2.4 Linked queue implement
> The following code is saved in `linked_queue.c`.
```c=
/* linked_queue.c */
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(void){
queuePoint front[MAX_QUEUE_SIZE];
queuePoint rear[MAX_QUEUE_SIZE];
element a = {10}, b = {20}, c = {30};
/* add */
addq(front, rear, 0, a); /* Front[0] = 10 = Rear[0] */
addq(front, rear, 0, b); /* Front[0] = 10 20 = Rear[0] */
addq(front, rear, 0, c); /* Front[0] = 10 20 30 = Rear[0] */
printLinkedQueue(front, 0); /* Front[0] = 10 20 30 = Rear[0] */
/* delete */
deleteq(front, 0); /* Front[0] = 20 30 = Rear[0] */
printLinkedQueue(front, 0); /* Front[0] = 20 30 = Rear[0] */
return 0;
}
```
## Sec. 4.4 Circular list
:::warning
原書章節為 Polynomial，此處省略關於多項式及其 linked list 的表示方法，只保留環狀串列(circular list)
:::
### 1. Representation of circular list
目前所提到串列架構都是最後一個節點有空鏈結(接地)的單向串列，這種型式的串列稱為鏈結串列(linked list)。
Linked list 有一個壞處是當我們需要刪除某個串列時，需要歷遍每個節點的位置才能清除串列，所以時間複雜度為 $O(n)$。基於這個原因，我們使用一種新的串列表示法，稱為環狀串列(Circular list)。
:::info
這邊指的清除串列不是釋放它的記憶體空間，而是類似初始化的概念。還是一樣會用到這些串列與節點，但儲存的值不太一樣。
:::
下圖所示為一個 circular list 的示意圖，與一般的 linked list 有兩個差異
* 最後一個節點指向開頭節點，形成環狀結構
* 使用一個指標指向最後的節點，而不是開頭節點
如同上面所說，我們需要釋出(非釋放)不需要使用的節點空間，並在之後需要時可以重新利用這些空間，這種方式藉由手動操作能夠更容易達到目的
### 2. Get and return node
假設 `avail` 指向一個 linked list，這個 list 是用來存放目前不需要使用的節點，並希望在未來需要時可以重新從這裡取得。
因此，當 `avail` 是空的就代表當前沒有可重複利用(reuse)的節點，需要重新分類記憶體空間。當 `avail` 非空就取出第一個節點重新使用。
透過以上想法，可以設計一個函式來取得可用節點
```c=
listPointer getNode(void){
listPointer node;
if avail {
node = avail;
avail = avail -> link;
}
else
MALLOC(node, sizeof(*node));
return node;
}
```
當某個節點不需要使用時，就將它釋放並添加到 `avail` 中，以方便未來能夠重複使用。要注意的是這邊重新添加到 `avail` 時是放到 `avail` 的開頭位置。
```c=
retNode(listPointer node){
node -> link = avail;
avail = node;
}
```
有了上述這兩個操作方式，就可以自行管理節點的新增與釋放，取代 `malloc()` 與 `free()`。
### 3. Delete circular list
如開頭所說，要清除一個串列需要歷遍整個串列才能做到，但如果使用 circular list 就可以做到無痛清除。
```c=
void cerase(listPointer *ptr){
if (*ptr){
temp = (*ptr) -> link;
(*ptr) -> link = avail;
avail = temp;
*ptr = NULL;
}
}
```
操作過程如下圖所示。核心概念就是將整個要清除的 circular list 加入到 avail 串列(的開頭)中，再把指向原串列的 ptr 刪除。
<!-- 放操作圖 -->
## Sec. 4.5 Others operation of list
### 1. Invert
第一個對於 linked list 的額外操作是反轉(invert)，將整個串列的順序顛倒。使用 3 個指標的方式進行可以做到空間複雜度為 $O(1)$，也就是不用額外的記憶體空間。
操作過程如上圖所示 :
* <font color="#FF0000">middle</font> 指向要回傳的串列
* 一開始需要初始化接地
* <font color="#FF8000">trail</font> 用來暫存 middle 的內容
* <font color="#FF0000">middle</font> 接收 lead 指向的節點，接收後 <font color="#0080FF">lead</font> 更新指向下一個節點
* 最後 middle 的<font color="#009100">後端</font>接收 trail
直到 lead 接地為止，整個串列反轉完成。
> The following code is saved in `OtherLinkedOperation.c`.
```c=
/* OtherLinkedOperation.c */
listPointer listInvert(listPointer lead){
/**
* lead is the linked list which we want to invert.
* middle is the linked list which save inverted list.
*/
listPointer middle, trail;
middle = NULL; /* initialize middle */
while (lead){
trail = middle;
middle = lead;
lead = lead -> link;
middle -> link = trail;
}
return middle;
}
```
#### 1.1 Implement of invert
> The following code is saved in `invert_list.c`.
```c=
/* invert_list.c */
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(void){
listPointer ptr;
listPointer invert;
ptr = Create2Node();
printList(ptr); /* data = 10, 20 */
invert = listInvert(ptr);
printList(invert); /* data = 20, 10 */
freeList(ptr);
return 0;
}
```
要注意的是因為只是做串列指向的反轉，並沒有更新每個節點的位址，所以最後釋放記憶體空間時只要釋放其中一個 `ptr` 或 `invert` 即可。
### 2. Concatenate
第二種額外操作是連接兩個串列，在連接之前，需找到第一個串列 ptr1 的尾端，找到才能將第二個串列 ptr2 銜接上去。在連接前也需要檢查這兩個串列是不是空的，如果是就不用連結，直接回傳另一個。
> The following code is save in `OtherLinkedOperation.c`.
```c=
/* OtherLinkedOperation.c */
listPointer concatenate(listPointer ptr1, listPointer ptr2){
listPointer temp;
if (!ptr1) return ptr2;
if (!ptr2) return ptr1;
/* find the last node of ptr1 */
for (temp=ptr1; temp -> link; temp = temp -> link);
/* concatenate */
temp -> link = ptr2;
return ptr1;
}
```
上面的程式碼中 for 迴圈代表的是一個空迴圈，因為內部沒有做任何事。
#### 2.1 Implement of concatenate
> The following code is saved in `concatenate.c`.
```c=
/* concatenate.c */
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(void){
listPointer ptr1, ptr2, temp, cont;
/**
* since the Create2Node() can create 2 node linked lists having same data.
* we must change one of their data field to distinguish it.
* finally, ptr1 = 10, 20 and ptr2 = 30, 40.
*/
ptr1 = Create2Node();
ptr2 = Create2Node();
for (temp = ptr2; temp; temp = temp -> link){
temp -> data = (temp -> data) + 20;
}
cont = concatenate(ptr1, ptr2);
printList(ptr1); /* data = 10, 20, 30, 40 */
freeList(ptr1);
return 0;
}
```
### 3. Operation of circular list
在環狀串列(circular list)中，我們使用了一個指標指向串列的最後一個節點，這種方式使得要插入節點到開頭或結尾時比較簡單。
如果是跟一般的 linked list 一樣，使用指向開頭的指標，那要插入節點到串列尾端會很麻煩，因為必須要歷遍整個串列直到尾端才能做到。
#### 3.1 Insert
有鑑於環狀串列的優勢，我們可以輕鬆的的插入節點到串列的頭部或尾端。插入開頭位置的過程如下圖所示。必須先將: (1) 尾部節點指向的開頭位址接上新節點(紅色部分)。(2) 再更新尾部節點指向新的開頭(藍色部分)
插入節點到尾端如下圖所示，基本上跟插入前端類似，不同的是最後需把指向尾端的 last 指標指向新的尾端。必須先將: (1) 指向頭部的尾端移動到新節點(藍色部分)。(2) 原來尾端指向新的節點(紅色部分)。(3) 將 last 指向新的尾端。
此外，這裡的實作上在插入節點前要注意兩件事 :
* 先建立環狀串列
* 插入節點時因為會改變指標指向的位址，所以函式參數需使用「指向指標的指標」來間接改變指向位址
> The following code is saved in `OtherLinkedOperation.c`.
```c=
/* OtherLinkedOperation.c */
listPointer createCircularList(){
listPointer first, second;
MALLOC(first, sizeof(*first));
MALLOC(second, sizeof(*second));
/* data */
first -> data = 10;
second -> data = 20;
/* link */
first -> link = second;
second -> link = first;
return second;
}
void insertFront(listPointer *last, listPointer node){
if (!(*last)){ /* pre is NULL */
*last = node;
node -> link = node;
}
else {
node -> link = (*last) -> link;
(*last) -> link = node;
}
}
void insertLast(listPointer *last, listPointer node){
if (!(*last)){ /* pre is NULL */
*last = node;
node -> link = node;
}
else {
node -> link = (*last) -> link;
(*last) -> link = node;
(*last) = node;
}
}
```
#### 3.2 Length
計算一個 circular list 的長度只需要歷遍每個節點的位置後再 +1 即可算出節點數量。
> The following code is saved in `OtherLinkedOperation.c`.
```c=
/* OtherLinkedOperation.c */
int length(listPointer last){
int count = 0;
listPointer temp = last;
do {
count++;
temp = temp -> link;
} while (temp != last);
return count;
}
```
#### 3.3 Implement of circular list
> The following code is saved in `circular_list.c`.
```c=
/* circular_list.c */
#include <stdio.h>
#include <stdlib.h>
#include "LinkedListADT.h"
int main(){
listPointer last;
listPointer front, behind;
int len;
/* initialize node */
MALLOC(front, sizeof(*front));
MALLOC(behind, sizeof(*behind));
front -> data = 0;
behind -> data = 30;
front -> link = NULL;
behind -> link = NULL;
/* insert */
last = createCircularList(); /* data = 10, 20 */
insertFront(&last, front); /* data = 0, 10, 20 */
insertLast(&last, behind); /* data = 0, 10, 20, 30 */
len = length(last);
printf("Length = %d\n", len); /* length = 4 */
return 0;
}
```
:::info
在環狀串列中，有時會額外增加一個標頭節點(header node)來更好的讓串列做運算(Ex: 多項式的串列表示法需要使用標頭節點來表示零或零多項式)
標頭節點的 data field 一般不會設定數值，但方便起見有時會將標頭節點的 data field 數值設為 -1
:::
## Sec. 4.6 Doubly linked list
不論是 linked list 還是 circular list，缺點顯而易見都會發生在插入與刪除的狀況，不論是插入或刪除串列中的某個定節點，幾乎都必須從頭開始走訪每個節點的位置，才能找到要插入/刪除的位置。
但這種缺點使用雙向鏈結串列(doubly linked list)可以很好的改善。雙向鏈結串列中，每個節點都會指向他的前一個節點以及後一個節點，因此可以有雙向的走訪方式。雙向鏈結串列的示意圖如下。
> The following code is saved in `LinkedListADT.h`.
```c=
/* for doubly linked list */
typedef struct node *nodePointer;
struct node {
int data;
nodePointer llink, rlink;
};
```
### 1. Insert
在 doubly linked list 中進行插入時以下圖為例，要將 newNode 插入到 frontNode 的右側位置。
從上圖可以看到在插入的過程中，新的節點會多產生 4 條 link 來跟左右兩個節點做連接，所以只要處理完這 4 條 link 就可以完成插入。原則上是先接新的 link 後再修改舊的 link。
* 先接新的
* newNode 向左指
* newNode 向右指
* 再改舊的(先斷後再接前)
* behindNode 向左指
* frontNode 向右指
```c=
void dinsert(nodePointer frontNode, nodePointer newNode){
newNode -> llink = frontNode;
newNode -> rlink = frontNode -> rlink;
frontNode -> rlink -> llink = newNode;
frontNode -> rlink = newNode;
}
```
### 2. Delete
刪除特定節點如下圖所示，因為會涉及到兩個 links 的重新連接與修改，所以只要處理完這兩個 links 就可以完成刪除的操作。此外，刪除節點不像插入需要涉及刪除位置的前一個，只要傳入欲刪除的節點就可以。
* frontNode 指向 behindNode(藍色箭頭)
* behindNode 指向 frontNode(紅色箭頭)
```c=
void ddelete(nodePointer ptr, nodePointer deleteNode){
deleteNode -> rlink -> llink = delete -> llink;
deleteNode -> llink -> rlink = delete -> rlink;
free(delete);
}
```
Sign in with Wallet
Connect another wallet