# 介紹
## 存儲結構
鏈表（Linked List）：是一種 `非連續`、`非順序` 存儲的線性結構。
鏈表由一個個的 `節點` 組成，每個節點在內存中 `位置是隨機` 不確定的（并不是順序的）。為了讓節點之間有聯系，在每個節點中都有一個指針指向下一個節點。
## 特點
`高效` 的 插入、刪除操作。（只需要修改指針的反向即可， 不需要移動數據）
`低效` 的 隨機讀取一個元素。（只為沒有下標，所以我們必須通過鏈表頭一個一個節點的向下查找想要的元素）
高效的插入：
添加新節點只需要：
1. 將上一個節點指向新節點
2. 將新節點指向下一個節點
圖標：向兩個紅色節點中插入一個新藍色節點：
## 類型
鏈表又可以分為：
- 單向鏈表
- 雙向鏈表
- 循環鏈表
- 雙向循環鏈表
單鏈表
循環鏈表：
雙向鏈表
雙向循環鏈表
# 代碼實現
在 JS 語言中沒有提供鏈表這種數據結構（Java 中提供了），所以當我們需要使用這種數據結構時，我們需要自己實現一套鏈表功能。
比較適合使用 "面向對象" 的方式來實現。
JS 中的面向對象有兩種寫法：
## 寫法一、傳統的寫法 （使用 function 定義類）
定義類時兩大原則：
1. 使用 function 來定義類
2. 類中的方法定義在原型上（prototype）
如下圖的寫法和下面 ES6 中的寫法功能完全相同：
## 寫法二、ES6 中新語法 （使用 class 定義類）
~~~
// 定義一個節點類
class Node {
constructor(data) {
this.data = data
this.next = null
}
}
// 鏈表類（管理所有的節點）
class LinkedList {
constructor() {
this.length = 0 // 鏈表中節點的數量
this.head = null // 鏈表的頭節點
this.tail = null // 指向最后一個節點
}
// 向鏈表的最后添加一個元素
append(data) {
// 1. 先創建一個新節點
let newNode = new Node(data)
// 2. 把這個新節點掛到鏈表的最后
// 如果當前鏈表是空，那么這個新節點即是頭節點，又是尾節點
if(this.tail === null) {
this.head = newNode
this.tail = newNode
} else {
// 讓尾節點的 next 指向新節點（掛到最后）
this.tail.next = newNode
// 讓tail指向指向這個新的節點（這個新節點現在是尾節點了）
this.tail = this.tail.next
}
// 鏈表長度+1
this.length++
}
// 清除鏈表
clear() {
this.length = 0
this.head = null
this.tail = null
}
// 刪除第 index 個節點
delete(index) {
// 1. 先找到第 index - 1 個節點（前一個節點）
let prev = this.getNodeByIndex(index-1)
// 2. 讓它的前一個節點的 next 指向，當前這個節點的 next
prev.next = prev.next.next
// 3. 長度-1
this.length--
}
// 根據下標找一個節點
getNodeByIndex(index) {
// 要查找的下標是否在鏈表范圍內
if(index > this.length - 1) return null
// 從頭節點開始向后跳 index 次
let current = this.head // 頭節點
for (let i = 0; i < index; i++) {
// 當前節點指向下一個節點
current = current.next
}
return current
}
// 把鏈表轉成一個字符串，打印時看著好看
toString() {
let ret = ''
if(this.length === 0) return ''
// 取出第一個節點
let current = this.head
// 把節點數據拼到字符串上
ret += current.data + '->'
// 循環鏈表中所有的節點并輸出
while (current.next !== null) {
// 當前節點指向下一個節點
current = current.next
// 取出節點上的數據拼到字符串上輸出
ret += current.data + '->'
}
return ret + 'null'
}
}
~~~
測試代碼：
~~~
// 創建一個鏈表
const lb = new LinkedList()
// 向鏈表中追回幾條記錄
lb.append('a')
lb.append('b')
lb.append('c')
lb.append('d')
lb.append('hello')
lb.append('boy')
// 打印鏈表結構
console.log(lb.toString())
lb.delete(4) // 刪除第5個元素：hello
console.log(lb.toString())
~~~
運行結果：
~~~
刪除前：
a->b->c->d->hello->boy->null
刪除后：
a->b->c->d->boy->null
~~~
