2020年5月26日

[資料結構] Linked List

      ,  
此系列筆記主要依照 [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

資料結構（Data Structure）是什麼

  • 不同的資料結構有不同的強弱項，有的在儲存（storing）和紀錄（recording）資料的速度較快，有的則是在搜尋（searching）和提取（retrieving）上比較快。
  • 資料結構的使用會影響到效能表現（performance）和程式運行的效率

Linked List

Imgur
  • Linked List 中，會紀錄該 Linked 的 head 和 tail
  • 每一個 Node 則會紀錄它的 value, prev 和 next
  • 其中會包含的方法為:
    • addToHead, addToTail
    • removeHead, removeTail
    • search, indexOf

Big O Notation

Constant Time - O (1)

  • 新增／移除 Head
  • 新增／移除 Tail

Linear Time - O (n)

  • 搜尋元素是否存在
  • 搜尋元素的 index 位置

Memory Manage Benefits

使用 Linked List 的資料結構可以更有效率的使用記憶體，因為每一個元素都是獨立，彼此之間是透過 next 和 prev 來關聯在一起：
Imgur

Sample Code

data-structures-in-javascript @ PJCHENder Github

Started Template

/* eslint-disable */
function LinkedList() {
  this.head = null;
  this.tail = null;
}

function Node({ value, next, prev }) {
  this.value = value;
  this.next = next;
  this.prev = prev;
}

// 輸入 value 後，把該值添加到 Linked List 的最前方
LinkedList.prototype.addToHead = function addToHead(value) {
  /* ... */
};

// 輸入 value 後，把該值添加到 Linked List 的最後方
LinkedList.prototype.addToTail = function addToTail(value) {
  /* ... */
};

// 移除 Linked List 的第一個 Node，若 Head 存在則回傳被移除的值，否則回傳 null
LinkedList.prototype.removeHead = function removeHead() {
  /* ... */
};

// 移除 Linked List 的最後一個 Node，若 Head 存在則回傳被移除的值，否則回傳 null
LinkedList.prototype.removeTail = function removeTail() {
  /* ... */
};

// 輸入 value 後，搜尋此 LinkedList 中是否有此值
// 找不到的話回傳 null，否則回傳找的的值
LinkedList.prototype.search = function search(searchValue) {
  /* ... */
};

// 列出所有等同於 searchValue 的 indexes
LinkedList.prototype.indexOf = function indexOf(searchValue) {
  /* ... */
};

module.exports = {
  LinkedList,
  Node,
};

參考

0 意見:

張貼留言