Linked List - HackMD

--- title: Linked List tags: Sprout C, Data Structure description: View the slide with "Slide Mode". --- ## Linked List 簡報：hackmd.io/@jason1024/S11BErB3S [ www.ppt.cc/fhX56x ] ---- ## Slido Be free to ask questions! 提問：app.sli.do/event/q0ai2mvx [ www.ppt.cc/fAPs2x ] --- #### 已經學過的資料結構 ## 陣列 Array ---- #### 缺點 ### 長度固定 ![](https://i.imgur.com/dgQ7Hog.jpg =380x) ---- #### ~~找飯店 ?~~ ## ~~Trivago !~~ ---- #### 需要動態長度的資料結構？ ## Linked List ! --- ### 想法 #### 利用動態記憶體配置擴增長度 #### 再把記憶體們串起來！ ![](https://i.imgur.com/UO0x1K5.png) ---- ### 需要增加長度時 #### 先宣告一塊新的記憶體 ![](https://i.imgur.com/BMemZmd.png) ---- ### 需要增加長度時 #### 再連接（Link）起來 ![](https://i.imgur.com/oZIJq9w.png) ---- ![](https://i.imgur.com/oZIJq9w.png) ### 恭喜你得到一條 Linked List ! --- #### 如何實作？ ### 利用指標記住下個記憶體的位置！ ---- #### 事前準備 ##### 結構宣告 ```cpp struct node { int data; // 要存的資料，型別、數量不拘 node *next; // 宣告指標準備做一個 Link 的動作 }; ``` ---- #### 事前準備 ##### 記住頭尾的位置 ```cpp node *head = NULL; node *rear = NULL; /* 分別用兩個指標 head 跟 rear 記住 linked list 頭尾的位置初始值設為 NULL (尚無節點) */ ``` ---- #### 事前準備 ##### 記憶體宣告函式 ```cpp node *newNode(int data){ node *res = new node; res->data = data; res->next = NULL; // 初始化 next 為 NULL } ``` ---- #### 操作 ##### 尾端插入 ```cpp void insertRear(int data){ if(head == NULL) head = rear = newNode(data); else{ rear->next = newNode(data); // 讓原本的最後一個節點的 next 指向新的尾巴 rear = rear->next // 讓 rear 這個指標指向新的尾巴 } } ``` ---- #### 操作 ##### 遍歷 ```cpp node *getNode(int index){ node *res = head; // 這裡讓 head 的 index 為 0 // 注意不要對 NULL 取值！ for(int i = 0; i < index && res != NULL; i++) res = res->next return res } ``` ---- #### 動動腦 ##### 利用 Linked List 實作 Queue 跟 Stack ---- ##### 用 Linked List 實作 Queue #### 新的值插在尾巴，取值由頭取 ```cpp node *pop(){ node *res = head; if(head != NULL) head = head->next; // 將 head 指向新的頭 return res; } ``` ---- ##### 用 Linked List 實作 Stack #### 新的值插在頭，取值由頭取 ```cpp void push(int data){ node *newHead = newNode(data); newHead->next = head; // 新頭的 next 指向原本的 head head = newHead; // 讓 head 指向後來的頭 } ``` --- ### 伴隨而來的優點 #### 快速刪除任意位置的值 ---- ##### 刪除任意位置的值：陣列 ### 將後面的值全部往前搬 ---- ##### 刪除任意位置的值：Linked List ### 讓前一個節點的 next 指向自己的 next ![](https://i.imgur.com/CURrdB9.png) ---- ##### 刪除任意位置的值：Linked List ### 讓前一個節點的 next 指向自己的 next ![](https://i.imgur.com/8pABHgt.png) ---- ##### 動動腦 ### 在任意位置插入？ ---- ##### 動動腦 ### 在任意位置插入？ ```cpp void insert(node *pos, node *insert){ insert->next = pos->next pos->next = insert } ``` ---- ##### 因為要存取到前一個節點的值所以每次都要再從頭遍歷一次？ #### 把前一個節點也記下來就好了 ```cpp struct node{ int data; node *prev, *next; // prev 指向上一個節點，next 指向下一個節點。 } ``` ---- ## Double Linked List ! #### 同樣的原理但要維護的值變多了 --- ## Comparison #### Array & Linked List ---- ### Array #### 優點：隨機存取、省空間 #### 缺點：長度固定、任意插入／刪除慢 ---- ### Linked List #### 優點：長度可變動、任意插入／刪除快 #### 缺點：需要空間去存記憶體位置、循序存取 --- ## </slide> ### 提問時間

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.