# [資料結構] Linked List

## 前言
* 特別注意，我們學校的資料結構課程其實沒有教這個......直接當作我們已經會了，所以寫得不夠好的話請見諒。
* 這東西寫久了，有時候結構中一些小地方會莫名其妙和別人不太一樣。
* 然後不得不說，這東西的概念一定要懂，實作也一定要實際去做，不然到後面Tree的node連結你八成也搞不懂。
* 好了，正文開始。
---

## 陣列？動態陣列？Linked List？
* 首先，不知道陣列是什麼的可以左轉了。
* 這就是一個大小為`5`的簡單陣列：

int arr[5];

* 那什麼是動態陣列？今天如果有一到題目，先給你數字`n`，再給你`n`個數字$A_1,A_2,...A_n$，那你要怎麼把數字存到陣列中呢？
* 新手大多會這樣做：

int n, arr[10000];
cin >> n;
for(int i = 0; i < n; i++)
    cin >> arr[i];

* 也就是事先給一個超大的記憶體空間，但這樣你自己也知道有問題。
* 數量超過10000就爆了(你用更大也一樣，都有個極限)。
* 如果數量只有10，你直接就浪費了9990個空間大小。
---
* 實際上你可以這樣：

int n;
int *arr = NULL;
cin >> n;
arr = new int[n];
for(int i = 0; i < n; i++)
    cin >> arr[i];

* 也就是說，arr一開始是一個沒有意義的指標。
* 而當你確認好空間實際上要多少之後，再和記憶體去要空間出來。
* 然而使用上面的動態陣列依然在某些情況會不太優秀。
* 如果我需要頻繁地新增、刪除資料，這時候你有兩種做法：
* 每次資料有所變更時都重新用新空間。
* 時間成本太高。
* 一次給多一點空間，當容量不夠時再擴大。
* 其實C++內建的vector就是這種方式，但依然會浪費掉一點點的空間。
---
* 這時候就該用**Linked List**了，它的概念是一次只給一格的空間，然後利用**指標**把每個空間都串起來。

digraph list
{
    node[shape="box"]
    data1->data2->data3
    {rank=same;data1;data2;data3}
}

* 看起來就像是火車的車廂一樣，一節拉著一節。
* 實作方式就是每組節點(node)裡面放你的資料和一個指標，用於指向下一個node的位置。

## 實作Linked List
* 實作Linked List的時候最好旁邊放紙筆一邊畫圖一邊做，否則容易搞混或忘記重設指標。
* 在這邊，我們加入資料和刪除資料的方式採用[Queues](/a56ukb7bS_SaekF3j2KlGA)的先進先出。
* 定義node：

struct node
{
    int data;
    node *next;
}

* 定義queue：

struct queue
{
    node *front;    //開頭，刪除的地方
    node *rear;    //結尾，加入的地方
    int size;    //裡面有幾筆資料
}

* 宣告並初始化queue：

queue q;
q.front = q.rear = NULL;    //一開始沒有資料，都先設為NULL指標。
q.size = 0;

* 加入：

void Push(queue &q, int v)
{
    node *n = new node;
    n->data = v;
    n->next = NULL;
    if(q.front == NULL)    //queue是空的
    {
        q.front = q.rear = n;
    }
    else
    {
        q.rear->next = n;    //先將尾巴接上去
        q.rear = n;        //再將queue的尾巴移到正確位置
    }
    q.size++;
}

* 刪除：

int Pop(queue &q)
{
    if(q.front == NULL)
        return -1;    //沒有元素在這個queue
    int v = q.front->data;
    q.front = q.front->next;    //將開頭移至下一個節點
    return v;
}

* 輸出：

void Display(queue &q)
{
    for(node *n = q.front; n != NULL; n = n->next)
        cout << n->data << endl;
}

* 如此一來，我們就完成了queue by Linked List。

### 完整的Linked List
* 上面的code由於是queue的型態，你會發現我們只能於開頭或結尾操作元素，但實際上我們是可以做到以下幾種事情的：
* 給予數字`v`，在linked list中搜尋後(回傳是第幾個位置/刪除它)。
* 給予數字`v`和位置`index`，將`v`插入到`index`的位置。(前提是已經有`index`以上的資料量了)。
* 因為懶得重打，就延續剛剛queue的結構。
* 回傳：
* 就一個一個找。

int Search(queue &q, int v)
{
    int count = 0;
    for(node *n = q.front; n != NULL; n = n->next)
    {
        if(n->data == v)
            return count;
        count++;
    }
    return -1;
}

* 剩下的code我懶ㄉ打了。
* 刪除：
* 找到目標節點後，將原本指向它的改為指向next node。
* 需特別注意如刪除開頭和結尾要更改queue的front和rear。

digraph list {
	node[shape=record]
    subgraph cluster_level1
    {
    label="刪除前"
	node1 [label=" <f0>Data1|<f1>●"];
    node2 [label=" <f0>Data2|<f1>●"];
    node3 [label=" <f0>Data3|<f1>●"];
    }
    node1:f1->node2:f1->node3:f1
    
    subgraph cluster_level2
    {
    label="刪除後"
	node1b [label=" <f0>Data1|<f1>●"];
    node2b [label=" <f0>Data2|<f1>●"];
    node3b [label=" <f0>Data3|<f1>●"];
    }
    node1b:f1->node2b:f1->node3b:f1[color="White"]
    node1b:f1->node3b:f1
}

* 插入也是差不多的概念：
* 將上一個節點的指標指向自己，然後將自己指向原本的下一個。
* 同樣須注意開頭和結尾。

digraph list {
	node[shape=record]
    subgraph cluster_level1
    {
    label="插入前"
	node1 [label=" <f0>Data1|<f1>●"];
    node2 [label=" <f0>Data2|<f1>●"];
    node3 [label=" <f0>Data3|<f1>●"];
    node4 [label=" <f0>Data2.5|<f1>●"];
    }
    node1:f1->node2:f1->node3:f1
    
    subgraph cluster_level2
    {
    label="插入後"
	node1b [label=" <f0>Data1|<f1>●"];
    node2b [label=" <f0>Data2|<f1>●"];
    node3b [label=" <f0>Data3|<f1>●"];
    node4b [label=" <f0>Data2.5|<f1>●"];
    }
    node1b:f1->node2b:f1->node4b:f1->node3b:f1;
}

## 其他資源
* 我當初大一是自己看這個學的：
* [C 語言：鏈結串列(Linked List)的建立與刪除](https://kopu.chat/2017/06/02/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97linked-list%E7%9A%84%E5%BB%BA%E7%AB%8B%E8%88%87%E5%88%AA%E9%99%A4/)
* [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) [name=宅色夫 jserv]

###### tags: `DS` `note`