Docker
Network
RxJS
Nginx
TypeScript
Data Structure And Algorithm
JavaScript
PostgreSQL
React
Git資料結構筆記-單向鏈結串列(Singly linked list)
Singly linked list 是 Linked listed 中最基本的版本，在這條 Link 上，每一個節點都儲存著資料 (val) ，且節點之間只能單向溝通 (由 head 至 tail )，透過 JavaScript 中的 Class 可以用來實現這樣的資料結構，如下方 code ，建立了兩個 class ( Node & SinglyLinkedList ) ，而 SinglyLinkedList 即本體，內部可由多個 Node 所連結而成，每個 Node 可存放val以及通往下個 Node 的 property (val, next) 。
Singly Linked List 的基本方法
- Push Method: 在 List 的後端 (tail) 新增一個新的節點 (Node) 。
- Pop Method: 將 List 尾端 Node 去除。
- Shift Method: 將 List 最前端 Node 去除。
- Unshift Method: 在 List 最前端新增一個 Node 。
- Get Method: 回傳在 List 中的特定的 Node
- Set Method: 修改 List 中特定 Node 的值
- Insert Method: 在 List 插入特定 index 的 Node 。
- Removed Method: 刪除 List 中特定 index 的 Node 。
1. Push Method
2. Pop Method
3. Shift Method
4. Unshift Method
5. Get Method
Set Method
Insert Method
Remove Method
同場加映 Reverse Method
意即將整個 linked list 反轉，一開始先將 head 以及 tail 互換，在 for loop 過程中， i= 0 的情況下， temp=this.tail ，但 temp.next 仍指向值為 2 的 node ，因此先將 temp.next 存放在 next 的變數，再將 prev (null) 傳入 temp.next ( 意即將 temp.next 指向 null ) ，為了下一步 ( i= 1 ) 做準備，故將 temp 傳入 prev ，將 next 傳入 temp 。
單向鏈結串列 (Singly Linked List) 的時間複雜度
當一組資料需要頻繁的在前端或尾端 ( head, tail ) 進行新增 ( Insertion ) 或是刪除 ( Removal ) 的動作時， Singly Linked List 可以是個很好的替代方案 (相較於使用 Array 而言) ，原因在針對 Array 進行前端的新增 (Array.shift()) 或刪減 (Array.unshift()) 時， Array 上所有的資料次序會因此變動( a[1] -> a[0] , a[2]-> a[1]...)，因此時間複雜度為 O (n) ，若是透過 Singly Linked List 來操作時，時間複雜度為O (1) 。
| Data Structure | Insertion | Removal | Searching | Access |
|---|---|---|---|---|
| Singly Linked | O(1) | O(1)或O(n) | O(n) | O(n) |