[資料結構] Linked-List — 鏈結串列

Linked List 為抽象的資料結構，概念有點像三國的連環船，一艘船(節點)連結著下一艘船(節點)，每個節點除了擁有自己的值之外也記錄自己的下一個節點是指向哪個節點，而 Linked List 又分為下列幾種

Simple Linked List

單向的 Linked List，最後一個節點 next 指向 null

Circular Linked List

最後一個節點的 next 指向第一個，形成一個循環

Doubly Linked List

雙向的 Linked List，可以看到節點除了紀錄 next 指向誰，也會記錄是誰指向自己

Linked List v.s Array

Linked List 為不連續的記憶體空間，因此在存放每個元素的同時 ，也會記錄下一個元素存放的位置，但假設今天想要取得鏈結串列的最後一個元素時 ，就必須從第一個元素開始讀取， 逐一讀到最後一個，讀取效率較為不理想，但是做插入和刪除資料的時候非常快，時間複雜度只有 O(1)。

Array 為連續的記憶體空間，所以可以直接用索引(index)來取得需要的值 ，讀取相當的快，不過假如要刪除一個元素或新增一個元素都會影響到其他元素的排序，統一往後或是往前挪，因此時間複雜度為 O(n)，n 為陣列長度。

那甚麼時候該用 Linked List 呢?

不需要快速的查詢資料以及有頻繁新增刪除資料的需求

用 js 實作 Linked List

創建一個 linked list，初始節點的值為 apple 並且將 next 指向 banana

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor(value) {
    //初始的節點命名為head
    this.head = new ListNode(value);
  }
  add(value) {
    const newNode = new ListNode(value);
    //head的next指向新的節點
    this.head.next = newNode;
    console.log("head", this.head);
  }
}

let linkedList = new LinkedList("apple");
linkedList.add("banana");

成功做出一個 Linked List!