链表
基本概念
链表又称单链表、链式存储结构，用于存储逻辑关系为“一对一”的数据。
使用链表存储数据，不强制要求数据在内存中集中存储，各个元素可以分散存储在内存中。
链表存储数据间逻辑关系的实现方案是：为每一个元素配置一个指针，每个元素的指针都指向自己的直接后继元素，如下图所示：
链表组成结构：节点（结点）
链表由节点构成，每个节点由两部分组成：数据域和指针域。
数据域用来存储元素的值，指针域用来存放指针。
一个完整的链表应该由以下几部分构成：
- 头指针：一个和结点类型相同的指针，它的特点是：永远指向链表中的第一个结点。上文提到过，我们需要记录链表中第一个元素的存储位置，就是用头指针实现。
- 结点：链表中的节点又细分为头结点、首元结点和其它结点：
- 头结点：某些场景中，为了方便解决问题，会故意在链表的开头放置一个空结点，这样的结点就称为头结点。也就是说，头结点是位于链表开头、数据域为空（不利用）的结点。
- 首元结点：指的是链表开头第一个存有数据的结点。
- 其他节点：链表中其他的节点。
也就是说，一个完整的链表是由头指针和诸多个结点构成的。每个链表都必须有头指针，但头结点不是必须的。
例如，创建一个包含头结点的链表存储 {1,2,3}，如下图所示
再次强调，头指针永远指向链表中的第一个结点。换句话说，如果链表中包含头结点，那么头指针指向的是头结点，反之头指针指向首元结点。
JS实现链表
需要注意链表的不同插入方法：尾部插入、头部插入、指定元素后面插入、指定元素前面插入
class Node {
constructor(val) {
this.val = val
this.next = null
}
}
class LinkedList {
constructor() {
// 头结点为空节点
this.head = new Node(null)
this.length = 0
}
// 从尾部插入节点
append(val) {
let newNode = new Node(val)
if (this.head.next === null) { // 空链表
this.head.next = newNode
} else { // 找到尾节点
let lastNode = this.head.next
while (lastNode.next !== null) {
lastNode = lastNode.next
}
lastNode.next = newNode
}
}
// 从头部插入
appendFromHead(val) {
let newNode = new Node(val)
if (this.head.next === null) {
this.head.next = newNode
} else {
let tmp = this.head.next
this.head.next = newNode
newNode.next = tmp
}
}
// 从指定元素后面插入
appendAfterElement(val, element) {
let node = new Node(val)
if (this.head.next === null) { // 链表为空
this.head.next = node
} else {
// 遍历链表找到element元素
let target = null
let tmp = this.head.next
while (tmp) {
if (tmp.val === element) {
target = tmp
break
}
tmp = tmp.next
}
if (!target) {
console.log('未找到目标节点');
return
}
let next = target.next
target.next = node
node.next = next
}
}
// 从指定元素前面插入
appendBeforeElement(val, element) {
let node = new Node(val)
if (this.head.next === null) { // 链表为空
this.head.next = node
} else {
// 遍历链表找到element元素
let target = null
let tmp = this.head.next
let pre = this.head
while (tmp) {
if (tmp.val === element) {
target = tmp
break
}
pre = tmp
tmp = tmp.next
}
if (!target) {
console.log('未找到目标节点');
return
}
pre.next = node
node.next = target
}
}
// 删除节点
remove(element) {
let curr = this.head.next
let pre = this.head
while (curr !== null) {
if (curr.val === element) {
pre.next = curr.next
return
}
pre = curr
curr = curr.next
}
console.log('节点不存在');
}
// 打印链表
print() {
let arr = []
let node = this.head
do {
arr.push(node)
node = node.next
} while (node)
console.log(arr);
}
}
let linkedList = new LinkedList()
linkedList.append(1)
linkedList.append(2)
linkedList.appendFromHead(0)
linkedList.appendAfterElement(1.5, 1)
linkedList.appendBeforeElement(0.5, 1)
linkedList.remove(1)
linkedList.print()
双向链表
单链表的每个结点再增加一个指向其前趋的指针域 pre，这样形成的链表有两条不同方向的链，称之为双向链表。
特点：
- 双链表一般也由头指针head唯一确定。
- 每一结点均有：
- 数据域(value)
- 左链域(pre)指向前趋结点.
- 右链域(next)指向后继。
- 是一种对称结构（既有前趋势，又有后继）
- 双链表的前插和后插难度是一样的。
缺点：指针数的增加会导致存储空间需求增加；二是添加和删除数据时需要改变更多指针的指向。
节点结构
class Node {
constructor(value) {
this.value = value;
this.next = null;
this.pre = null;
}
}