# 介绍
## 存储结构
链表（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
~~~
