[資料結構] Array and Linked List

TL;DR

Singly Linked List

• 每個 Node 會包含 value 和 next 的資訊
• Linked List 會包含 head, tail 的資訊
• Linked List 包含 append, prepend, insert, remove, printList 的方法

class NodeType {
  value: number;
  next: NodeType | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  head: NodeType;
  tail: NodeType;
  length: number;
  constructor(value: number) {
    const theNode = new NodeType(value);
    this.head = theNode;
    this.tail = theNode;
    this.length = 1;
  }

  append(value: number) {}
  prepend(value: number) {}
  insert(index: number, value: number) {}
  remove(index: number) {}
  printList() {}
  private traverseToIndex(index: number) {}
}

Doubly Linked List

• 每個節點（Node）包含了 next, prev 和 value
• Linked List 會紀錄 head, tail 的資訊
• Linked List 實作了 append, prepend, insert, remove printList 的方法

class NodeType {
  value: number;
  next: NodeType | null;
  prev: NodeType | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

class DoublyLinkedList {
  head: NodeType;
  tail: NodeType;
  length: number;
  constructor(value: number) {
    const newNode = new NodeType(value);
    this.head = newNode;
    this.tail = newNode;
    this.length = 1;
  }

  append(value: number) {}
  prepend(value: number) {}
  insert(index: number, value: number) {}
  remove(index: number) {}
  private traverseToIndex(index: number) {}
  printListFromHead() {}
  printListFromTail() {}
}

export {};

Doubly Linked List

• Singly Linked List 和 Doubly Linked List 的差別在於，Singly Linked List 的每一個 Node 只會紀錄 next 是誰，因此只能從頭開始一路往後；而 Double Linked List 在 Node 中則會同時紀錄 next 和 previous，因此可以由後往前找：
  • Singly List 使用較少的記憶體空間，appen 和 prepend 時會快一些，但沒辦法從後往前 traverse，search, insert, delete 會花比較多時間
  • Doubly Linked List 使用較多的記憶體空間，append 和 prepend 會比較慢一些，但可以由前往後 traverse，search, insert, delete 時會花較少時間
• Doubly Linked List 和 Array 有一個差異在於，Array 會被配置到一連串的記憶體空間，而 Linked List 的各個節點（Node）則是會分散在記憶體的不同位置，因此在做疊代（iterate）的時候，相較之下速度會稍微慢些。
• Doubly Linked List 和 Hash Table（相較於 Array）都較容易進行增減，但 Linked List 又多了順序的概念。
• Linked List 和 Array 雖然都有順序的概念在，但如果我們想要直接從某個 Node 開始往前或往後找時，Linked List 會比 Array 容易（例如，瀏覽器的上一頁或下一頁）
• Doubly Linked List 中，會紀錄該 Linked 的 head 和 tail
• 每一個 Node 則會紀錄它的 value, prev 和 next
• 其中會包含的方法為:
  • addToHead, addToTail
  • removeHead, removeTail
  • search, indexOf

Big O Notation

Constant Time - O (1)

• prepend：新增／移除 Head
• append：新增／移除 Tail

Linear Time - O (n)

• lookup：搜尋元素是否存在、搜尋元素的 index 位置
• Insert, delete：元素的新增和刪除

提示

雖然 doubly linked list 和 singly linked list 在 Time Complexity 上的 Big O Notation 是相同的，但實際上 doubly linked list 會更快一些。

Memory Manage Benefits

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

Array 和 Linked List 的差別

	Linked List	Array
說明	類似把很多個物件關聯起來，並有順序性	同一記憶體空間的一個區間
記憶體	不需要連續的記憶體空間，因此不需要預留空間	需要連續的記憶體空間，宣告時就需要決定空間大小
資料插入/刪除	相對快，插入和刪除本身是 O(1)，但有時需要先搭配搜尋 O(n) 來找到節點位置	相對慢，插入與刪除均為 O(n)
資料取出	相對慢，要從頭開始找 O(n) 到後取出	相對快，可以直接使用索引（index）取出
適用時機	1. 無法預期資料數量時 2. 需要頻繁增刪資料時 3. 不需要頻繁查詢並取出資料時	1. 需要快速取出資料時 2. 不需要頻繁增刪資料時 3. 資料的數量不會有太大變更時

資料整理自：ALPHA Camp

Sample Code

data-structures-in-javascript @ PJCHENder Github

Singly Linked List

class NodeClass {
  value: number;
  next: NodeClass | null;
  constructor(value: number) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  head: NodeClass;
  tail: NodeClass;
  length: number;

  constructor(value: number) {
    const newNode = new NodeClass(value);
    this.head = newNode;
    this.tail = newNode;
    this.length = 1;
  }

  append(value: number) {
    const newNode = new NodeClass(value);
    // this.tail 是指稱到某個 Node
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

  prepend(value: number) {
    const newNode = new NodeClass(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }

  insert(index: number, value: number) {
    const newNode = new NodeClass(value);
    const temp = this.traverseToIndex(index - 1);
    newNode.next = temp.next;
    temp.next = newNode;

    return this;
  }

  remove(index: number) {
    const temp = this.traverseToIndex(index - 1);
    if (temp.next === null) {
      throw new Error('the index is over the length of linked list');
    }
    temp.next = temp.next.next;
  }

  private traverseToIndex(index: number) {
    let temp = this.head;
    let i = 0;
    while (i !== index) {
      if (temp.next === null) {
        throw new Error('the index if over the length of linked list');
      }
      temp = temp.next;
      i++;
    }

    return temp;
  }

  printList() {
    const list: number[] = [];
    let currentNode: NodeClass | null = this.head;
    while (currentNode !== null) {
      list.push(currentNode.value);
      currentNode = currentNode.next;
    }
    return list;
  }
}

// 2 -> 3 -> 1 -> 10 -> 5 -> 16
const myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);
myLinkedList.prepend(1);
myLinkedList.prepend(2);
myLinkedList.insert(1, 3);
myLinkedList.remove(3);
console.log(myLinkedList.printList());

Doubly Linked List - 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,
};

參考

• Master the Coding Interview: Data Structures + Algorithms by Andrei Neagoie @ Udemy
• Learning Data Structures in JavaScript from Scratch by Eric Traub @ Udemy
• 鏈結串列 Linked List @ iT 邦鐵人賽 by hannahpun