\# js数据结构 链表
\### 链表和数组
数组其实是一种线性表的顺序储存结构，他的特点是用一组地址连续的存储单元依次存储数据元素。他的缺点也是他的特点造成的，比如对数组作删除或者插入的时候，可能需要移动大量的元素
大致模拟一下数组的插入操作
```
function insert(arr, index, data) {
for (let i = arr.length; i > index; i --) {
arr\[i\] = arr\[i - 1\]
}
arr\[index\] = data
}
```
从上面的操作可以看出数组的插入以及删除都可能会是一个O(n)的操作。从而就引出了链表这种数据结构，链表不要求逻辑上相邻的元素在物理位置上也相邻，因此他没有顺序存储结构所具有的特点，当然它也就失去了数组在一路爱连续空间随机存取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
链表存储的是有序的元素集合，和数组不同的是，链表中的元素在内存中并不是连续放置，每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。
链表有很多中类型：单向链表、双向链表、循环链表
!\[链表.png\](https://image-static.segmentfault.com/121/123/1211231093-5c7120816b7f8\_articlex)
和数组相比，链表的优势在于：添加或者删除元素不需要移动其他元素，劣势是在与链表相对于数组结构更复杂，需要一个指向下一个元素的指针，在访问链表中的某个元素也需要从头迭代，而不是像数组一样直接访问
\### 链表的特点
线性表的链式存储表示的特点是用一组任意的：存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 与其直接后继数据元素 之间的逻辑关系，对数据元素 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"，表示线性表中一个数据元素。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。
存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。
由分别表示,，…，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。
\### 单向链表
!\[链表.png\](https://segmentfault.com/img/bVblRLN?w=587&h=95)
\##### 单向链表的特点：
\- 用一组任意的内存空间去存储数据元素（这里的内存空间可以使连续的，也可以是不连续的）
\- 每个节点（node）都由数据本身和一个指向后续节点的指针组成
\- 整个链表的存取必须从头指针开始，头指针指向第一个节点
\- 最后一个节点的指针指向空（NULL）
\##### 链表中的几个主要操作：
\- 创建节点
\- 插入节点
\- 搜索/遍历节点
\- 删除节点
\- 合并
\##### 初始化节点
\- 指针指向空
\- 存储数据
```
class Node {
constructor(key) {
this.next = null;
this.key = key;
}
}
```
\##### 初始化单向链表
\- 每个链表都有一个头指针，指向第一个节点，没节点则指向NULL
```
class List {
constructor () {
this.head = null
}
```
\##### 创建节点
```
//类（class）通过 static 关键字定义静态方法。不能在类的实例上调用静态方法，而应该通过类本身调用。
//这些通常是实用程序方法，例如创建或克隆对象的功能。
//通过static向外暴露了一个静态方法来创建节点，而并非直接将他封装金插入操作中。
//创建一个链表 -> 创建一个节点 -> 将节点插入进链表中
static createNode(key) {
return new createNode(key);
}
```
\##### 插入节点（插入到头节点后）
插入操作只需要去调整节点的指针即可，两种情况:
\- head没有指向任何节点，说明当前插入的节点是第一个
1. head指向新节点
2. 新节点的指针指向NULL
\- head有指向的节点
1. head指向新的节点
2. 新节点的指针指向原本head所指向的节点
```
insert(node) {
//如果head有指向的节点
if(this.head) {
node.next = this.head;
} else {
node.next = null
}
this.head = node
}
```
\##### 搜索节点
\- 从head开始查找
\- 找到节点中的key等于想要查找的key的时候，返回该节点
```
find(key) {
let node = this.head
while(node !== null && node.key !== key) {
node = node.next
}
return node
}
```
\##### 删除节点
分三种情况
\- 所要删除的节点刚好是第一个,也就是head指向的节点
将head指向所要删除节点的下一个节点（node.next）
\- 要删除的节点为最后一个节点
寻找到所有删除节点的上一个节点（prevNode)
将prevNode中的指针指向null
\- 在列表中间删除某个节点
寻找到所要删除节点的上一个节点（prevNode)
将prevNode中的指针指向当前要删除的这个节点的下一个节点
```
delete(node) {
//第一种情况
if (node === this.head) {
this.head = node.next
return;
}
//查找所要删除节点的上一个节点
let prevNode = this.head;
while (prevNode.next !== node) {
prevNode = prevNode.next
}
//第二种情况
if (node.next === null) {
prevNode.next = null
}
//第三种情况
if (node.next) {
prevNode.next = node.next
}
}
```
\#### 单向链表整体代码
```
class ListNode {
constructor(key) {
this.next = null;
this.key = key;
}
}
class List {
constructor() {
this.head = null;
this.length = 0
}
}
static createNode(key) {
return new ListNode(key)
}
insert(node) {
//如果head后面有指向的节点
if (this.head) {
node.next = this.head
} else {
node.next = null
}
this.head = node
this.length ++
}
find(key) {
let node = this.head
while (node !== null && node.key !== key) {
node = node.next
}
return node
}
delete(node) {
if (this.length === 0) {
throw 'node is undefined'
}
if (node === this.head) {
this.head = node.next
this.length --;
return
}
let prevNode = this.head
while (prevNode.next !== node) {
prevNode = prevNode.next
}
if (node.next === null) {
prevNode.next = null
}
if(node.next) {
prevNode.next = node.next
}
this.length --
}
```
