• 跟 Array 非常類似，但有些不一樣

  • linear collection

  • java 裡面如果寫 java 比較複雜，你要告訴 java 說這個 array 長度是多少

    • javascript 為什麼不需要設定 array 的長度有多少？

  • Linkeded List 在記憶體裡面位置是不連續的

  • 實際上只有兩個 property， head 跟 length

    • 會透過連接 value 及 next(一個 node 裡面會包含這兩個)

    • head 指向第一個 value 後，next 會指向下一個 value

    • 最後一個 next 沒有值了就指向 null

    • 多指一個後，length + 1

  • advantages

    • array 的話在一開始就已經定義了長度

      • linked list 一開始不會設定長度多少，會從 0 開始

    • 跟 array 相比 linked list 在做 insertion 跟 deletion 非常的快

      • 刪掉某一個值或是新增某一個值的速度會被 array 快很多

      • 對於 linked list 來說刪除跟新增就是指向給替換一下就好

      • 刪除 array 的話是清除之後其他都往上提一格（所有 index 的直都要改變）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Node {
  constructor(value){
    this.value = value;
    this.next = null;
  }
}


class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  push(value){
    let newNode = new Node(value);
    if(this.head === null){
        this.head = newNode;
        this.
     } else {
      let currentNode = this.head;
      while (currentNode.next !== null){
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
     }
     this.length++;
  }

  printAll() {
    if(this.length === 0){
      console.log("Nothing in this linked list.");
      return;
    }
    let currentNode = this.head;
    while(currentNode !== null){
      console.log(currentNode.value);
      currentNode = currentNode.next;
    }
  }
}

let myLinkedList = new LinkedList();
myLinkList.push("Vic");
myLinkList.push("Ash");
myLinkList.push("Ip Man");

  • 要知道怎麼用 javascript 寫出 LinkedList 的應用，包括 pop、Shift、Unshift、LnsertAt、removeAt、get

  • disadvantages（基本上都是跟 array 相比)

    • 跟 array 比起來會用更多記憶體的空間

      • 原因是儲存時會用到 pointers( next property

    • Linked List 一定要從頭開始閱讀

      • 都要從 head 走起( sequential access)

    • noncontiguous

      • 不是連續性的，增加找的時間

    • reverse traversing 很難

      • cumbersome

      • 但是 array 很簡單

Array 跟 Linked List 比較

Linked List

  • Do Not Have indices

    • 沒有 index

  • Connection between nodes are a “next” pointer

    • 依靠 next 來連結每個 node

  • Random access is not allowed(Must go through each item before accessing)

    • 沒辦法直接跳到某一個，要從頭找

Array

  • Items are indexed in oreder

    • 有 index

  • Insertion and delertion are expensive

    • 很貴代表代價高，因為要全部重新整理一遍

  • Elements can quickly be accessed with a specific index

    • 可以馬上跳到某個值

時間複雜度

Accerssing Elements

要找到某一個 index number

Array → O(1)

Linked List → O(n)

Insert and Remove from the Beginning

其實就是 shift 跟 unshift

Array → O(n)

Linked List→ O(1)

Insert and Renove from the End

Array → O(1)

Linked List→ O(n)

Insert and Renove from the Middle

Array → O(n)

Linked List→ O(n)

可以從上面發現一件事情

O(n) 的數量 Array 有兩個，Linked List 有三個，其他都是 1。但這樣代表 Array 比較好嗎？ 也不一定，看情況

如果你很常用到 lsert 跟 remove from the Beginning 的情境，那 Linked List 會比較好

Doubly Linked List

上面提到的都是 Singly Linked List

但世界上還存在一種叫做 Doubly Linked List

Doubly Linked List 會指出兩個 pointer
除了 next 之後還有 before，可以指向下一個，也能指向上一個

好處

找一個值，時間是 Singly Linked List 的一半

壞處

記憶體會消耗更多

它跟 Singly Linked List 最大的差異就是：可以 雙向遍歷