# 資料結構與演算法搭配 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/)