object and array 可以完成所有要做的事情，但某些時後它的時間複雜度會很大。學習資料結構可以去降低我們的複雜度。

linked list 連結串鏈

與 array 類似

1. a linked list is a linear collection of data elemenets whose order is not given by their physical value placement in memory. Instead, each element points to the next. 資料是用線性方式串在一起、他們的順序非依照電腦記憶體物理順序，所有的 element 都有 pointer 指向下一個 element。

// 在其他語言，要做出 array 要先宣告陣列的長度
// java
myArr = new String[10] // 宣告陣列的長度是 10
電腦會在記憶體位置找到十個相鄰空間，給 myArr 做使用

js 底層有 space doubling 也就是當 array 的長度再增加，它也會再增加記憶體的長度

array element 在電腦記憶體位置是一一被排好的

1. data structure contains that only head and length property.(linked list 的資料結構只有兩個 property：head, length)
2. Linked list consists of nodes and each node has a value(number, string, array, or anything) and a pointer to another node or null.(linked list 是由很多個 nodes 組成，nodes 包含兩部分 value and pointer)

• node 包含兩部分，node 包含兩部分，value、next
• mike、james、peter 在記憶體位置不連續
• 如果要再增加長度，先在電腦記憶體某個地方，先做一個 node，這個 node 它的 next 會指向 null，把原本 linked list 的最後一個指向 null 的值，改指向新作的 node 的 value。同時回頭改 linked list 的長度，變成 4。

與 array 的相異點

1. 順序：linked list 不像 array 在電腦記憶體做連續排序，linked list的順序在記憶體排序是不連續的
2. 運作原理

小結

linked list 是一種資料結構，包含兩個 properties：head and length。

advantages of linked list

1. elements can be inserted into linked list indefinetely, while an array will eventually either fill up or need to be resized.
2. vary fast insertion and deletion compared to array

優點一

• linked list 一開始並未設定長度，長度從 0 開始，每加入一個新的 node 到 linked list，他的長度就再加一。 => 不斷加入新的 node 是沒有問題的 !
• array 一開始就定義長度(ex: js let arr = [ ] 他的最大長度是 1，加入更多的值進去長度會變成 2、4、8、16、32 ...)，假設 array 已被填滿它的長度是 8，若想加入第九個值到 array，js 會額外配置八個記憶體空間，所以現在 array 的總長度是 16。若加入第十七個值，array 的長度又會 double，所以 array 的長度會變成 32 => 這些 element 都是被整齊排序，所以要加入更多的值，就必須將 array 的長度不斷擴大。

優點二

• linked list 舉例、要把 james 的值刪掉，不需要將他從記憶體裡面排除，只要將 Harry 的 next 指向 Ron 就好。只要將 pointer 改變就可以輕鬆完成 insertion and deletion。
• array 舉例、若想將移除第 n 個值，要 n 之後的值全部往上移一格。所以做 insertion and deletion 相當不方便。因為所有 index 的值都要改變。

Linked list push

1. 寫 node, 裡面有兩個 property (value, next)
2. 建立 linked list
3. linked list 裡面加入新的 node => 用 push 這個 method，(value) 設定
4. newNode 進行初始化
5. 考慮將新的值放進來會有甚麼情況 => 測試

• 情況一、linked list 長度 0 裡面沒有東西，所製作的 newNode 會變成這個 linked list 的 head
• 情況二、linked list 裡面已有東西，將 linked list 最後一個 node 的 next 指向新增 node 的 value

class Node {
  constructor(value) {
    // 初始化 node 值
    this.value = value
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.head = null
    this.length = 0
  }
  push(value) {
    let newNode = new Node(value) //執行 Node class 的 constructor，所以 newNode 透過 Node 的 constructor 進行初始化
    if (this.head === null) {// this 是 LinkedList
      this.head = newNode
      this.length++
    } else {
      let currentNode = this.head // 目前在的位置
      while(currentNode.next !== null) {
        currentNode = currentNode.next
      }
      currentNode.next = newNode
      this.length ++
    }
  }
  printAll() {
    if (this.length === 0) {
      return console.log('nothing in this linked list')
    }
    let currentNode = this.head
    while (currentNode !== null) {
      console.log(currentNode.value)
      currentNode = currentNode.next
    }
  }
}

// 測試
let myLinkedList = new LinkedList()
myLinkedList.push('apple')
myLinkedList.push('bag')
myLinkedList.push('car')
myLinkedList.push('duck')

myLinkedList.printAll()
console.log(myLinkedList.length)