## 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 ---- #### 缺點 ### 長度固定  ---- #### ~~找飯店 ?~~ ## ~~Trivago !~~ ---- #### 需要動態長度的資料結構？ ## Linked List ! --- ### 想法 #### 利用動態記憶體配置擴增長度 #### 再把記憶體們串起來！  ---- ### 需要增加長度時 #### 先宣告一塊新的記憶體  ---- ### 需要增加長度時 #### 再連接（Link）起來  ----  ### 恭喜你得到一條 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  ---- ##### 刪除任意位置的值：Linked List ### 讓前一個節點的 next 指向自己的 next  ---- ##### 動動腦 ### 在任意位置插入？ ---- ##### 動動腦 ### 在任意位置插入？ ```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> ### 提問時間