# 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;
}
}
```
Sign in with Wallet
Connect another wallet