---
# System prepended metadata

title: Chap. 04 - Linked List
tags: [資料結構]

---

# 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)，用來指向下一個節點的位址

![未命名](https://hackmd.io/_uploads/Hk7IIbrg1e.png)

如上圖所示，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 是空的。


![img](https://hackmd.io/_uploads/B1qqq6rxyg.jpg)

#### 2.1 Insertion

Linked list 的優勢在於可以用簡單的步驟來進行==對任意位置插入節點==，以下圖為例，要在一個 linked list 中插入 "mat" 字串 :

![img](https://hackmd.io/_uploads/ByS1aarlke.jpg)

* 產生一個新的節點(data+link)並用指標 paddr 指向這個新的節點
* 將字串 "mat" 寫入到 data field
* 將 paddr 的 link field 指向下一個節點(sat)的位址
* 前一個節點(cat)的 line field 指向新的節點 paddr

#### 2.2 Deletion

Linked list 刪除特定位址的節點時，也==不用作任何的資料搬移==，以下圖為例，要刪除 linked list 中的 "sat" 字串 :

![img](https://hackmd.io/_uploads/SJghpTBlyl.jpg)

* 找到欲刪除節點的前一個節點(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` 表示第一個節點的位址是空的，意即沒有任何節點存在。以圖示表示的話代表直接接地，如下圖所示。

![image](https://hackmd.io/_uploads/HJkdp-Llye.png)

產生節點的方式可以使用 `malloc()` 等函式來動態分配一段記憶體，且記憶體大小空間為 `sizeod(*first)`。因為 `first` 變數的資料型態是指向 listNode 結構的指標，所以當使用 `*` 運算子時表示取出 `first` 指標所指向的內容，也就是 listNode 結構，因此 `sizeof(*first)` 代表的是 lintNode 結構的大小。當然，也可直接使用 `sizeof(listNode)` 來計算 linstNode 結構的大小。

創建完節點後再對該節點的 data field 與 link field 賦值。因為是單一節點，所以節點後沒有其他節點，link field 直接設為 `NULL` 表示接地。單一節點的 linked list 的示意圖如下圖。

![image](https://hackmd.io/_uploads/HJ7-7G8eJe.png)

> 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;
}
```

##### 插入節點的過程示意圖如下所示

![img](https://hackmd.io/_uploads/H1ou_Mcx1l.jpg)

> 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`) ?**

當傳遞指標時，函數內部是==傳遞指標的副本==，對指標所指向的位址有改變的話不會傳遞到外面。只有對這個指標使用 `*` 運算後，指標所指向位址的內容的改變才會傳遞到函數外部。
如果需要改變指標指向的位址，需要傳遞指向這個指標的指標，再透過 `*` 運算來修改第一個指標的位址，使他指向別的資料。(參見下圖)

![S__2408451](https://hackmd.io/_uploads/S1tuqz5gkx.jpg)

:::

##### 刪除節點的過程示意圖如下所示

![img](https://hackmd.io/_uploads/HkSt4ungke.png)

> 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 的方式串聯起來。

![image](https://hackmd.io/_uploads/SyOemyRlkl.png)

如上圖所示，每個 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，如下圖所示

![S__2433032](https://hackmd.io/_uploads/BkdWhDOZ1x.jpg)


#### 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 端都要指向新的節點，如下圖所示。

![S__2433036](https://hackmd.io/_uploads/rk1qiP_Zyx.jpg)

> 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 類似，記得要先取值，再斷開(刪除)鏈結，如下圖所示。

![S__2433037](https://hackmd.io/_uploads/S1Yy2vOZyl.jpg)


> 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 有兩個差異

* 最後一個節點指向開頭節點，形成環狀結構
* 使用一個指標指向最後的節點，而不是開頭節點

![S__2457603](https://hackmd.io/_uploads/SkdNN-ZGye.jpg)

如同上面所說，我們需要釋出(非釋放)不需要使用的節點空間，並在之後需要時可以重新利用這些空間，這種方式藉由手動操作能夠更容易達到目的

### 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)$，也就是不用額外的記憶體空間。

![S__2457604](https://hackmd.io/_uploads/BkVUPbbf1x.jpg)

操作過程如上圖所示 :

* <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) 再更新尾部節點指向新的開頭(藍色部分)

![S__2457606](https://hackmd.io/_uploads/Hkd1yzWzkl.jpg)

插入節點到尾端如下圖所示，基本上跟插入前端類似，不同的是最後需把指向尾端的 last 指標指向新的尾端。必須先將: (1) 指向頭部的尾端移動到新節點(藍色部分)。(2) 原來尾端指向新的節點(紅色部分)。(3) 將 last 指向新的尾端。

![S__2457607](https://hackmd.io/_uploads/HJUyxfWG1g.jpg)

此外，這裡的實作上在插入節點前要注意兩件事 :

* 先建立環狀串列
* 插入節點時因為會改變指標指向的位址，所以函式參數需使用「指向指標的指標」來間接改變指向位址

> 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

![S__2457613](https://hackmd.io/_uploads/r1D-Em_zyl.jpg)

:::

## Sec. 4.6 Doubly linked list

不論是 linked list 還是 circular list，缺點顯而易見都會發生在插入與刪除的狀況，不論是插入或刪除串列中的某個定節點，幾乎都必須從頭開始走訪每個節點的位置，才能找到要插入/刪除的位置。

但這種缺點使用雙向鏈結串列(doubly linked list)可以很好的改善。雙向鏈結串列中，每個節點都會指向他的前一個節點以及後一個節點，因此可以有雙向的走訪方式。雙向鏈結串列的示意圖如下。

![S__2457614](https://hackmd.io/_uploads/HypGr7ufJe.jpg)

> 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 的右側位置。

![S__2457615](https://hackmd.io/_uploads/SJI5r7ufJl.jpg)

從上圖可以看到在插入的過程中，新的節點會多產生 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 就可以完成刪除的操作。此外，刪除節點不像插入需要涉及刪除位置的前一個，只要傳入欲刪除的節點就可以。

![S__2457616](https://hackmd.io/_uploads/rkb18X_fkg.jpg)


* frontNode 指向 behindNode(藍色箭頭)
* behindNode 指向 frontNode(紅色箭頭)

```c=
void ddelete(nodePointer ptr, nodePointer deleteNode){
    deleteNode -> rlink -> llink = delete -> llink;
    deleteNode -> llink -> rlink = delete -> rlink;
    free(delete);
}
```

