---
# System prepended metadata

title: 鏈結串列 Linked List
tags: [article]

---

---
title: 鏈結串列 Linked List
tags: article
---

# 前導：物件(Object)補充



### 物件(Object)的特點：

1. 物件可以定義變數(variables)和方法(methods)的存取權。
2. 物件可以繼承(inherit)自其他的class ─ 沿用原本的變數和方法。
3. 物件可以定義建構式(constructors)、解構式(destructors)、運算子(operators)等特殊方法。

---


### - 存取權(Accessibility)

在C++，一共分成三種存取權：public(公用)、private(私用)、protected(保護)

- <font color=blue>private：</font>其方法/變數，無法被直接存取，僅可由同一個物件內的方法來做存取。
- <font color=blue>public：</font>其方法/變數，可被直接存取。
- <font color=blue>protected：</font>規則與private近似，但繼承該物件的物件，可使用受保護的方法/變數。

> struct與class功能完全相同，僅差在預設存取權不同而已，
> class : private | struct : public
> 


文章參考：
 - [struct vs class in C++](https://blogs.sw.siemens.com/embedded-software/2014/06/02/struct-vs-class-in-c/)
 - [【class語法大全】(1) 物件導向概念; 封裝與存取權限; class基礎語法; 預設建構子與拷貝建構子](https://ithelp.ithome.com.tw/articles/10230401)

---

### - 方法(Method)：
我們通常會將一個物件之下的函式，稱作為方法(method)。
舉個簡單的例子：想像機器人是一個物件，可以設計一個機器人有諸如像是walk、shutdown之類的功能，這些功能即是機器人的方法。

```cpp
class Robot{
public:
    string name;
    int id;
    int position;
    bool turnoff;
    
    void walk(int d){
        positon += d;
    }
    
    void shutdown(){
        turnoff = true;
    }
};

// variables: name, id, position, turnoff
// methods: walk、shutdown
```
如果不想要在class裡面定義方法的功能，可以用下面舉例的方式來定義(這與上面的程式碼同義)：
```cpp
class Robot{
public:
    string name;
    int id;
    int position;
    bool inactive;
    
    void walk(int);
    void shutdown();
};

void Robot::walk(int d){
    positon += d;
}

void Robot::shutdown(){
    inactive = true;
}
```

---

### - 建構式與解構式(Constructor & Destructor)：

宣告一個新的物件時，會先執行constructor裡面的內容，
顧名思義，移除(delete)物件時，會執行destructor裡面的內容。
<font color=red>(！請注意！)</font> constructor和destructor不需要回傳型態，且名字與class或struct定義的名稱相同。
<font color=red>(！請注意！)</font> destructor的名稱前面必須要加「~」，且不能帶有參數。

下方舉例，以Profile儲存人名與年齡：
```cpp
class Profile{
public:
    string name;
    int age;
    
    Profile(){
        name = "empty";
        age = -1;
        cout <<"create an empty profile\n";
    }
    
    Profile(string n, int a){
        name = n;
        age = a;
        cout <<"create profile: "<< name << " (" << age << ")\n";
    }
    
    ~Profile(){
        cout <<"delete profile: "<< name << " (" << age << ")\n";
    }
};

int main(){
    Profile pf_a;                            // constructor: Profile()
    Profile pf_b;                            // constructor: Profile()
    Profile *pf_c = new Profile("Sam",20);   // constructor: Profile(name,age)
    delete pf_c;
    Profile pf_d("Josh", 18);                // constructor: Profile(name,age)
}
```
output :
```
create an empty profile
create an empty profile
create a profile: Sam (20)
delete a profile: Sam (18)
create a profile: Josh (18)
delete a profile: Josh (18)
delete a profile: empty (-1)
delete a profile: empty (-1)
```
> 如果沒定義constructor的話，編譯時編譯器會自動幫你寫一個：
> 將物件裡面的變數都設為0的constructor method。

文章參考：
- [OpenHome - 建構函式、解構函式](https://openhome.cc/Gossip/CppGossip/ConstructorDestructor.html)
---

### - 運算子重載(Operators Overloading)

藉由運算子重載，可以定義該物件經過運算子處理的部分，
其編譯器會將所有物件，預設一個等於(=)的運算子，
其功能是將等號右邊物件裡面的變數值存至等號左邊物件的變數中。

由於用法比較複雜，故以文章說明代替：
- [OpenHome - 運算子重載](https://openhome.cc/Gossip/CppGossip/OverloadOperator.html)


---

# 鏈結串列(Linked List)

一個最典型的資料結構，其圖(graph)非常簡單，
以下列出這些常見的串列(list)：

### 1. 單向鏈結串列 (Single Linked List)：
    每個節點可以 指向次節點 (next)

![](https://i.imgur.com/1W2UhJ4.png =500x)

### 2. 雙向鏈結串列 (Doubly Linked List)：
    每個節點可以 指向次節點和前節點 (next & prev)

![](https://i.imgur.com/b0MQYCe.png =800x)

### 3. 循環鏈結串列 (Circular Linked List)：
    串列的首尾相連，形成一個環

![](https://i.imgur.com/69phTTQ.png =400x)


```cpp
// the node structure of single linked list

class Node{
public:
    int value;
    Node *next;
};
```

```cpp
// the node structure of double linked list

class Node{
public:
    int value;
    Node *next;
    Node *prev;
};
```



文章參考：
 - [hackmd - [資料結構] Linked List](https://hackmd.io/@Zero871015/H12vTu8aX?type=view)
 - [Tutorialspoint - Data Structure and Algorithms - Linked List](https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm)
 - [演算法筆記 - Data](http://web.ntnu.edu.tw/~algo/Data.html#2)
 - [Geeks - Linked List Data Structure](https://www.geeksforgeeks.org/data-structures/linked-list/)
---

# 二元樹(Binary Tree)

## 結構(Structure)
二元樹的概念很簡單，就只是把原先Linked List的單一節點從單分支 變成 雙分支，
即樹的每個節點可以指向兩個子節點(children)，其兩個子節點分別為左和右節點 (left & right)
```cpp
// the node structure of binary tree

class Node{
public:
    int value;
    Node *left;
    Node *right;
};
```

![](https://i.imgur.com/KNUR3DS.png =350x) ![](https://i.imgur.com/mi7OCOQ.png =350x)
(還記得老大第一堂課在黑板上畫的右邊那張圖嗎？這就是一個二元樹)

> 我們通常會以一些名詞來形容一棵樹，像是root(根)、leaf(葉)、level(層數)...等，
> 詳細名詞可以參見此講義：[資訊之芽2021算法班 - Tree](https://www.csie.ntu.edu.tw/~sprout/algo2021/ppt_pdf/week02/tree.pdf)



文章參考：
 - [Geeks - Binary Tree Data Structure](https://www.geeksforgeeks.org/binary-tree-data-structure/)
 - [演算法筆記 - Binary Tree](http://web.ntnu.edu.tw/~algo/BinaryTree.html)
 - [資訊之芽2020講義 - Tree](https://www.csie.ntu.edu.tw/~sprout/algo2020/ppt_pdf/week02/tree.pdf)

---

# Problem Set

### Single Linked List
1. LeetCode : [237 - Delete Node in a Linked List](https://leetcode.com/problems/delete-node-in-a-linked-list/)
2. LeetCode : [21 - Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/)

### Double Linked List
1. Geeks Pratice : [Doubly linked list Insertion at given position ](https://practice.geeksforgeeks.org/problems/insert-a-node-in-doubly-linked-list/1)
2. Geeks Pratice : [Delete node in Doubly Linked List ](https://practice.geeksforgeeks.org/problems/delete-node-in-doubly-linked-list/1)


### Circular Linked List
1. LeetCode : [141 - Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
2. CSES : [Josephus Problem I](https://cses.fi/problemset/task/2162)

### Binary Tree
1. LeetCode : [938 - Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/)
( Q : How to traverse the whole binary tree? )
```












..........................................😀.........................................











```
---

# Hints

### Single Linked List
1. 由於並不知道前一個節點資訊，可以考慮對「當前的節點」進行處理，比如往後插入一個節點。

2. 迴圈每次只動一條的指標即可，如果僅用單個迴圈會太難想，不免將迴圈拆成3個迴圈來處理。

### Doubly Linked List
1. 在指定位置插入新節點。
   
2. 刪除指定位置的節點，推薦用圖示的方式來構想「刪除節點並串接左右兩側節點」的操作流程。

> Geeks初始設的建構式並不多，推薦可以外加一些方法/建構式來用。
> (ex. `void Node::insert(int x, Node* pv, Node* nx)` )

### Circular Linked List
1. 如果遇到走過的節點，即回傳true，重點在於要如何標示此點是否已被走過。

2. 用迴圈建構完Single Linked List後，只要將最後一個節點的next指向head，即可構成循環。
   此題不應使用Doubly Linked List，這只會使處理刪除節點的部分變得過於複雜而難以思考。

### Binary Tree
1. 提供一個簡單遍歷整棵樹的演算法概念：<font color=blue>深度優先搜索 DFS (Depth-First Search)</font>
   此演算法是以「先往左走再往右走」的遞迴方式，
   因其會不斷往左走，直到走到向左所能走的最深處時才會停止，故名為「深度優先」。
   
> 另有一個名稱類似的演算法：廣度優先搜索 BFS (Breadth-First Search)，
> 實作難度高於DFS，如果有興趣者可以搜尋看看其演算法的概念。

```cpp
// example code of the DFS function:

void dfs(Node* cur){
    if(cur == NULL)
        return;
        
    dfs(cur->left);
    dfs(cur->right);
}
```

 - DFS二元樹的遍歷：[Tree Traversals (Inorder, Preorder and Postorder)
](https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/)

###### posted date: `2021.3.24` 