---
# System prepended metadata

title: Singly Linked-list
tags: [tutorial]

---

# Singly Linked-list

###### tags: `tutorial`

[TOC]

## 簡介

Linked-list 是一種資料結構，利用指標把資料像火車一樣一節一節的連結在一起

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 12 | <ref>  }", width=1.2]
        b [label="{ <data> 99 | <ref>  }"];
        c [label="{ <data> 37 | <ref>  }"];
        null [shape=box];
        a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
        b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> null      [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        head -> a

}
```

每一節"車廂"我們叫作 node，可以根據想儲存的資料型式決定中間要有哪些資料，不過一定要有指標指到下一節的位置

因此 struct 可以宣告成這樣

```cpp=
struct Node {
    int data; // 這邊用 int 當範例，實際上不一定只能有一個 int
    Node* next;
};
```

這邊儲存一個 int 當作資料，用 next 當成指到下個資料的指標

## 建立 Linked list

### 概念

一開始我們要有一個指標，保存第1節的位置

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        head -> NULL
}
```

接下來宣告另一個指標做操作，並產生新的一節，把資料填進去

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        head -> NULL
        cur -> a
        a:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

把 head 指到第1節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        head -> a
        cur -> a
        a:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```
接下來要產生第 2 節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> a
        cur -> b
        a:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

把第1節的 next 指到第 2 節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> a
        cur -> b
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

第 3 節之後都是按照第 2 節的方法處理

### 程式碼實作

直接寫死

```cpp=
Node *head = NULL;
Node *cur = new Node();
cur->data = 5; // 這邊可以修改成你要的資料
cur->next = NULL;
head = cur;
cur = new Node();
cur->data = 6; // 這邊可以修改成你要的資料
cur->next = NULL;
head->next = cur;
```

連續操作

```cpp=
// 第1節
Node *head = new Node();
head->next = NULL;

Node *cur = head;
for(int i = 0; i < 5; ++i){ // 這邊可以修改成你要的判斷條件
    Node newNode = new Node();
    newNode->next = NULL;
    cur->data = i; // 這行可以改成你要插入的資料
    cur->next = newNode;
    cur = cur->next;
}
```

## 刪除 Linked list

### 概念

先用一個 cur 指標指到 head 的那一節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> a
        cur -> a
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

把 head 移到下一個

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> b
        cur -> a
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

釋放 cur

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> b
        cur
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

連續做到 head = NULL 為止

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        head ->  "NULL" 
}
```

### 程式碼實作

```cpp=
while(head != NULL){
    Node *cur = head;
    head = head->next;
    delete cur;
}
```

## 查詢資料

用一個 cur 指標，從 head 開始一個一個比較，如果不滿足條件就繼續找 next

```cpp=
Node *cur = head;
while(cur != NULL && cur->data != 6){ // 這邊可以修改成你要的判斷條件
    cur = cur->next;
}
```

找到的話 cur 會指到要找的 node，沒找到的話會指到 NULL;

## 插入節點

### 從頭插入

這是最簡單的插入方法，不過連續插入的話資料的順序會反轉

#### 概念

創建新的一節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        c [label="{ <data> 4 | <ref>  }", width=1.2]
        head -> a

        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        cur -> c
        c:ref:c -> "NULL" [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

把 cur 那節的 next 指到 head

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        c [label="{ <data> 4 | <ref>  }", width=1.2]
        head -> a

        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        cur -> c
        c:ref:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

把 head 指到 cur

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        c [label="{ <data> 4 | <ref>  }", width=1.2]
        head -> c

        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        cur -> c
        c:ref:c -> a [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

#### 程式碼實作

```cpp=
// 第1節
Node *cur = new Node();
cur->data = 4; // 這邊可以修改成你要的資料
cur->next = head;
head = cur;
```

### 從中間插入

這邊比較麻煩，要小心不要讓連結斷掉

#### 概念

創建 cur 指標，並且把 cur 移到要插入的位置

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 4 | <ref>  }", width=1.2]
        b [label="{ <data> 5 | <ref>  }", width=1.2]
        c [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> a
        cur -> b
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

再創建另一個指標，建立新的一節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 4 | <ref>  }", width=1.2]
        b [label="{ <data> 5 | <ref>  }", width=1.2]
        c [label="{ <data> 6 | <ref>  }", width=1.2]
        d [label="{ <data> 7 | <ref>  }", width=1.2]
        head -> a
        cur -> b
        "newNode" -> d
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

新的 next 指到 cur 的 next

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 4 | <ref>  }", width=1.2]
        b [label="{ <data> 5 | <ref>  }", width=1.2]
        c [label="{ <data> 6 | <ref>  }", width=1.2]
        d [label="{ <data> 7 | <ref>  }", width=1.2]
        head -> a
        cur -> b
        "newNode" -> d
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

cur 的 next 指到新的那節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 4 | <ref>  }", width=1.2]
        b [label="{ <data> 5 | <ref>  }", width=1.2]
        c [label="{ <data> 6 | <ref>  }", width=1.2]
        d [label="{ <data> 7 | <ref>  }", width=1.2]
        head -> a
        cur -> b
        "newNode" -> d
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> d [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        d:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

#### 程式碼實作

```cpp=
// 找到要的位置
Node *cur = head;
while(cur != NULL && cur->data != 5){ // 這邊可以修改成你要的判斷條件
    cur = cur->next;
}
Node *newNode = new Node();
newNode->data = 7; // 這邊可以修改成你要的資料
newNode->next = cur->next;
cur->next = newNode;
```

### 從尾巴插入

#### 概念

先創建 cur 指標，指到最後一節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> a

        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        cur -> b
}
```

直接用 cur 的 next 產生新的一節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        c [label="{ <data> 7 | <ref>  }", width=1.2]
        head -> a

        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        cur -> b
}
```

#### 程式碼實作

```cpp=
// 找到最尾
Node *cur = head;
while(cur->next != NULL){
    cur = cur->next;
}
cur->next = new Node();
cur->next->data = 7; // 這邊可以修改成你要的資料
cur->next->next = NULL;
```

### 完整插入

通常在用的時候不會知道是頭、中、尾，這是結合頭、中、尾三種方式的插入方法

#### 程式碼實作

```cpp=
// 找到最尾
Node *cur = head;
while(cur != NULL && cur->next != NULL && cur->data != 5){ // 這邊可以修改成你要的判斷條件
    cur = cur->next;
}
if(cur == NULL){ // 頭
    cur = new Node();
    cur->data = 5; // 這邊可以修改成你要的資料
    cur->next = head;
    head = cur;
}else if(cur->next == NULL){ // 尾
    cur->next = new Node();
    cur->next->data = 5; // 這邊可以修改成你要的資料
    cur->next->next = NULL;
}else{ // 中
    Node *newNode = new Node();
    newNode->data = 5; // 這邊可以修改成你要的資料
    newNode->next = cur->next;
    cur->next = newNode;
}
```

## 刪除節點

刪除的時候要小心不要讓連結斷掉

### 刪除第 1 節

#### 概念

:::info
其實就是前面刪除 Linked-List 的方法，只是不連續做而已
:::

先用一個 cur 指標指到 head 的那一節

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> a
        cur -> a
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

把 head 移到下一個

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> b
        cur -> a
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

釋放 cur

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        b [label="{ <data> 6 | <ref>  }", width=1.2]
        head -> b
        cur
        b:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

### 程式碼實作

```cpp=
Node *cur = head;
head = head->next;
delete cur;
```

### 刪除中間 & 尾巴

:::info
中間 & 尾巴方法一樣
:::

#### 概念

先用一個 cur 指標指到要刪的 **前** 一節

:::warning
**前** 一節!!!
**前** 一節!!!
**前** 一節!!!
:::

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2, color=red]
        c [label="{ <data> 7 | <ref>  }", width=1.2]
        cur [color=red]
        head -> a
        cur -> a
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

創一個新指標，指到要刪掉的 **那** 一節

:::warning
**那** 一節!!!
**那** 一節!!!
**那** 一節!!!
:::

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2, color=red]
        c [label="{ <data> 7 | <ref>  }", width=1.2]
        del [color=red]
        head -> a
        cur -> a
        del -> b
        a:ref:c -> b [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

cur 的 next 指到 del 的 next

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        b [label="{ <data> 6 | <ref>  }", width=1.2, color=red]
        c [label="{ <data> 7 | <ref>  }", width=1.2]
        del [color=red]
        head -> a
        cur -> a
        del -> b
        a:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        b:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

釋放 del

```graphviz
digraph foo {
        rankdir=LR;
        node [shape=record];
        head [shape=box];
        a [label="{ <data> 5 | <ref>  }", width=1.2]
        c [label="{ <data> 7 | <ref>  }", width=1.2]
        del [color=red]
        head -> a
        cur -> a

        a:ref:c -> c [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
        
        c:ref:c -> "NULL " [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
}
```

#### 程式碼實作

```cpp=
Node *cur = head;
// 找到位置
while(cur->next->next != NULL && cur->next->data != 6){ // 這邊可以修改成你要的判斷條件
    cur = cur->next;
}
Node *del = cur->next;
cur->next = del->next;
delete del;
```
### 完整刪除

```cpp=
// 找到最尾
Node *cur = head;
while(cur != NULL && cur->next != NULL && cur->data != 6 && cur->next->next != NULL && cur->next->data != 6){ // 這邊可以修改成你要的判斷條件
    cur = cur->next;
}
if(cur != NULL){ // 如果是 NULL 表示是空的
    if(cur->next == NULL || cur->data == 6){ // 第 1 節
        head = head->next;
        delete cur;
    }else{ // 中間或尾巴
        Node *del = cur->next;
        cur->next = del->next;
        delete del;
    }
}
```