---
# System prepended metadata

title: 資料結構與演算法搭配 leetcode - Day2

---

# 資料結構與演算法搭配 leetcode - Day2

`by Benben`

什麼是資料結構？

---

其實你已經至少兩種會了！
就是 Array 跟 Obejct

---

其他還有
- Linked List
- Queue / Stack
- Hash Table
- Tree
- Graph

---

為什麼我們需要這些資料結構？

所有的東西都是建立在需求上，
那還有其他資料結構嗎？

---

![](https://res.cloudinary.com/practicaldev/image/fetch/s--ZDtqrBOj--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://github.com/damiancipolat/js_vs_memes/blob/master/doc/js_thanks.png%3Fraw%3Dtrue)

---

為什麼需要 Linked List

---

Linked List

```javascript
function LinkedNode( val, next ){
  this.val = val || 0
  this.next = next || null
}
```

---

Linked List 的好處
1. 可以無限增加元素
2. 在執行 `插入` 跟 `刪除` 時特別快

---

Linked List vs Array

|  | Linked List | Array |
| -------- | -------- | -------- |
| C     | 1     | n     |
| R     | n     | 1     |
| U     | 1     | 1     |
| D     | 1     | n     |

---

```javascript
function LinkedNode( val, next ){
  this.val = val || -1
  this.next = next || null
}

// 新增元素
let list = new LinkedNode

let currentNode = list
while(currentNode.next !== null) {
  currentNode = currentNode.next
}
currentNode.next = new LinkedNode(3)
```

---

Liked List 的缺點
1. 許要更多的 memory
2. 一定要從頭開始讀，儲存方式是不連續的
3. 要反向讀取的話會很麻煩

---

進階的 Linked List : 
Doubly Linked List

---

Leetcode : 
21. Merge Two Sorted Lists
https://leetcode.com/problems/merge-two-sorted-lists/

---
live coding 解 :
```javascript

var mergeTwoLists = function(l1, l2) {
  let listNode = new ListNode
  
  let cur = listNode
  while(l1 && l2) {
    if(l1.val > l2.val) {
      cur.next = l2
      l2 = l2.next
    } else {
      cur.next = l1
      l1 = l1.next
    }
    cur = cur.next
  }
  cur.next = l1 || l2
  return listNode.next

};
```

---

Ref : 
- [資料結構與演算法 (JavaScript)](https://www.udemy.com/course/algorithm-data-structure/)
- [Leetcode](https://leetcode.com/)