A data structure that contains a head, tail and length.
Linked list consists of node, and each node has a value and a pointer to another node or null.
鏈結串列 Linked List
像一列沒有標記車廂號碼的火車，每一節都連在一起。不能隨機指定第幾節車廂。
陣列Array
像是電梯，按下按鈕(by index)可以直接抵達指定樓層。有 index 照順序，若有新增刪除的話會比 linked list 辛苦。
定義節點 Node
定義節點 Node 的 class，再去定義 Singly linked list 的 class。
定義 Singly linked list
之後會把各種操作加在裡面。
push
先帶入要 push 的值，創造一個新的 node 節點，如果沒有 head 節點的話，將此節點設定為 head，也設定為 tail，如果已經有 head 的話，把 tail.next 設定為此節點再將 tail 設定成 tail.next，整個 list 長度加一，最後回傳整個 list。
push(val){
var newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}pop
先確認有無 node 在 list 裡面，如果沒有任何 node 的話，回傳 undefined。遍歷過整個 list，直到碰到 tail。設定倒數第二個的 next 為 null。將倒數第二個值設定為 tail。整個跑完 list 長度扣一，若扣除到零，把 head 跟 tail 設定成 null(否則 head 跟 tail 還是會有 node(長度為零的時候))，最後回傳被 pop 掉的值。
pop() {
if(!this.head) {
return undefined;
}
var current = this.head;
var pre = current;
while(current.next) {
pre = current;
current = current.next;
}
this.tail = pre;
this.tail.next = null;
this.length--;
if(this.length === 0) {
this.head = null;
this.tail = null;
}
return current;
}shift
先確認有無 node 在 list 裡面，如果沒有任何 node 的話，回傳 undefined。將目前的 head 存到 current 變數中，將 this.current 設定成 current.next。整個跑完 list 長度扣一，最後回傳被 shift 掉的值。
shift() {
if(!this.head) {
return undefined;
}
var current = this.head;
this.head = current.next;
this.length--;
return current;
}unshift
先代入要 unshift 的值，創造一個新的 node 節點，如果沒有 head 節點的話，將此節點設定為 head，也設定為 tail 。如果已經有 head 的話，將新節點的 next 指向目前的 head，再將新節點設定為 head。整個 list 長度加一，最後回傳整個 list。
unshift(val) {
var newNode = new Node(val);
if(!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
var current = newNode;
current.next = this.head;
this.head = current;
}
this.length++;
return this;
}Get a value
此 function 需要接收一個 index，若 index 小於零或大於等於 list 長度，return null。遍歷整個 list 直到找到對應的 index，回傳該值。遍歷的過程：將 counter 設定為 0，current 指向 head，跑迴圈 current = current.next，count++。
get(index) {
if(index<0 || index>=this.length) return null;
let counter = 0;
let current = this.head;
while(counter !== index) {
current = current.next;
counter++;
}
return current;
}Set a value
此 function 接收一個 index 還有一個要被設定的值，使用 get function 去找到節點的位置，如果節點不存在 return false，找到節點的話將節點換成要設定的值，return true。
set(index,value) {
let foundNode = this.get(index)
if(!foundNode) return false;
foundNode.val = value;
return true;
}Inset a value
此 function 接收一個 index 還有一個要被插入的值，若 index 小於零或大於 list 長度，return false。如果 index 等於list長度，使用 push 並 return true。如果 index 等於 0，使用 unshift 並 return true。若非上述情況，使用 get 取得節點的前一個位置(因為 insert 要用到)，為待插入的值創造一個新的 node 節點。把該節點的 next 先用一個 temp 變數存起來，再將此節點的 next 設定給新節點，新節點的 next 設定為 temp，最後長度加一，return true。
insert(index,value) {
if(index<0 || index>this.length) return false;
if(index == this.length) {
this.push(value);
return true;
}
if(index == 0) {
this.unshift(value);
return true;
}
let newNode = new Node(value);
let previousNode = this.get(index-1);
let temp = previousNode.next;
previousNode.next = newNode;
newnode.next = temp;
this.length++;
return true;
}Remove a value
此 function 接收一個 index 還有一個要被插入的值，若 index 小於零或大於 list 長度，return false。如果 index 等於 list 長度 -1，使用 pop 並 return 該值。如果 index 等於0，使用 shift 並 return 該值。若非上述情況，使用 get 取得節點的前一個位置，並用 previousNode 變數存起。再將取得節點的 next 用一個 removed 變數存起來，previousNode.next = removed.next 即刪除 removed。最後長度扣一，return removed 值。
remove(index) {
if(index<0 || index>this.length) return false;
if(index == this.length-1 ){
return this.pop();
}
if(index == 0){
return this.shift();
}
let previousNode = this.get(index-1);
let removed = previousNode.next;
previousNode.next = removed.next;
this.length--;
return removed;
}
