---
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)
### 2. 雙向鏈結串列 (Doubly Linked List)：
每個節點可以 指向次節點和前節點 (next & prev)
### 3. 循環鏈結串列 (Circular Linked List)：
串列的首尾相連，形成一個環
```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;
};
```
 
(還記得老大第一堂課在黑板上畫的右邊那張圖嗎？這就是一個二元樹)
> 我們通常會以一些名詞來形容一棵樹，像是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`
Sign in with Wallet
Connect another wallet