在 Javascript 中学习数据结构与算法
这是一本5万字符（中文约2w）的小书，可能需要几个小时阅读，需要几天或更多时间去消化。部分代码还不能正确地跑起来，有错别字，有不准确的概念...，但这不妨碍它作为你一个野生前端学习数据结构与算法的启蒙文章，期待你的一针见血、刀刀致命😐
对任何专业技术人员来说，理解数据结构都非常重要。作为软件开发者，我们要能够用编程语言和数据结构来解决问题。编程语言和数据结构是这些问题解决方案中不可或缺的一部分。如果选择了不恰当的数据结构，可能会影响所写程序的性能。因此，了解不同数据结构和它们的适用范围十分重要。
一句话：算法即原力，即正义
本文主要讲述Javascript中实现栈、队列、链表、集合、字典、散列表、树、图等数据结构，以及各种排序和搜索算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、顺序搜索、二分搜索，最后还介绍了动态规划和贪心算法等常用的高级算法及相关知识。
在阅读之前假设你已了解并可以熟练使用Javascript编写应用程序。
概览
数据结构
- 栈：一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
- 队列：与上相反，一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。
- 链表：存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的；每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（指针/链接）组成。
- 集合：由一组无序且唯一（即不能重复）的项组成；这个数据结构使用了与有限集合相同的数学概念，但应用在计算机科学的数据结构中。
- 字典：以 [键，值] 对为数据形态的数据结构，其中键名用来查询特定元素，类似于 Javascript 中的
Object。 - 散列：根据关键码值（Key value）直接进行访问的数据结构；它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度；这个映射函数叫做散列函数，存放记录的数组叫做散列表。
- 树：由 n（n>=1）个有限节点组成一个具有层次关系的集合；把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的，基本呈一对多关系，树也可以看做是图的特殊形式。
- 图：图是网络结构的抽象模型；图是一组由边连接的节点（顶点）；任何二元关系都可以用图来表示，常见的比如：道路图、关系图，呈多对多关系。
算法
排序算法
- 冒泡排序：比较任何两个相邻的项，如果第一个比第二个大，则交换它们；元素项向上移动至正确的顺序，好似气泡上升至表面一般，因此得名。
- 选择排序：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，以此循环，直至排序完毕。
- 插入排序：将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，此算法适用于少量数据的排序，时间复杂度为 O(n^2)。
- 归并排序：将原始序列切分成较小的序列，只到每个小序列无法再切分，然后执行合并，即将小序列归并成大的序列，合并过程进行比较排序，只到最后只有一个排序完毕的大序列，时间复杂度为 O(n log n)。
- 快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行上述递归排序，以此达到整个数据变成有序序列，时间复杂度为 O(n log n)。
搜索算法
- 顺序搜索：让目标元素与列表中的每一个元素逐个比较，直到找出与给定元素相同的元素为止，缺点是效率低下。
- 二分搜索：在一个有序列表，以中间值为基准拆分为两个子列表，拿目标元素与中间值作比较从而再在目标的子列表中递归此方法，直至找到目标元素。
其他
贪心算法：在对问题求解时，不考虑全局，总是做出局部最优解的方法。
动态规划：在对问题求解时，由以求出的局部最优解来推导全局最优解。
复杂度概念：一个方法在执行的整个生命周期，所需要占用的资源，主要包括：时间资源、空间资源。
数据结构
栈
栈是一种遵从先进后出 (LIFO) 原则的有序集合；新添加的或待删除的元素都保存在栈的末尾，称作栈顶，另一端为栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。
通俗来讲，一摞叠起来的书或盘子都可以看做一个栈，我们想要拿出最底下的书或盘子，一定要现将上面的移走才可以。
栈也被用在编程语言的编译器和内存中保存变变量、方法调用。
在 Javascript 中我们可以使用数组的原生方法实现一个栈/队列的功能，鉴于学习目的，我们使用类来实现一个栈。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
class Stack {
constructor() {
this.items = []
}
// 入栈
push(element) {
this.items.push(element)
}
// 出栈
pop() {
return this.items.pop()
}
// 末位
get peek() {
return this.items[this.items.length - 1]
}
// 是否为空栈
get isEmpty() {
return !this.items.length
}
// 尺寸
get size() {
return this.items.length
}
// 清空栈
clear() {
this.items = []
}
// 打印栈数据
print() {
console.log(this.items.toString())
}
}
使用栈类：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
// 实例化一个栈
const stack = new Stack()
console.log(stack.isEmpty) // true
// 添加元素
stack.push(5)
stack.push(8)
// 读取属性再添加
console.log(stack.peek) // 8
stack.push(11)
console.log(stack.size) // 3
console.log(stack.isEmpty) // false
队列
与栈相反，队列是一种遵循先进先出 (FIFO / First In First Out) 原则的一组有序的项；队列在尾部添加新元素，并从头部移除元素。最新添加的元素必须排在队列的末尾。
在现实中，最常见的例子就是排队，吃饭排队、银行业务排队、公车的前门上后门下机制...，前面的人优先完成自己的事务，完成之后，下一个人才能继续。
在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档。
同样的，我们在 Javascript 中实现一个队列类。
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
class Queue {
constructor(items) {
this.items = items || []
}
enqueue(element){
this.items.push(element)
}
dequeue(){
return this.items.shift()
}
front(){
return this.items[0]
}
clear(){
this.items = []
}
get size(){
return this.items.length
}
get isEmpty(){
return !this.items.length
}
print() {
console.log(this.items.toString())
}
}
使用队列类：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
const queue = new Queue()
console.log(queue.isEmpty) // true
queue.enqueue('John')
queue.enqueue('Jack')
queue.enqueue('Camila')
console.log(queue.size) // 3
console.log(queue.isEmpty) // false
queue.dequeue()
queue.dequeue()
queue.print() // 'Camila'
优先队列
队列大量应用在计算机科学以及我们的生活中，我们在之前话题中实现的默认队列也有一些修改版本。
其中一个修改版就是优先队列。元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇(或 带小孩的妇女)登机时也享有高于其他乘客的优先级。
另一个现实中的例子是医院的(急诊科)候诊室。医生会优先处理病情比较严重的患者。通常，护士会鉴别分类，根据患者病情的严重程度放号。
实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除它们。在下面示例中，我们将会在正确的位置添加元素，因此可以对它们使用默认的出列操作：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
class PriorityQueue {
constructor() {
this.items = []
}
enqueue(element, priority){
const queueElement = { element, priority }
if (this.isEmpty) {
this.items.push(queueElement)
} else {
const preIndex = this.items.findIndex((item) => queueElement.priority < item.priority)
if (preIndex > -1) {
this.items.splice(preIndex, 0, queueElement)
} else {
this.items.push(queueElement)
}
}
}
dequeue(){
return this.items.shift()
}
front(){
return this.items[0]
}
clear(){
this.items = []
}
get size(){
return this.items.length
}
get isEmpty(){
return !this.items.length
}
print() {
console.log(this.items)
}
}
优先队列的使用：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
const priorityQueue = new PriorityQueue()
priorityQueue.enqueue('John', 2)
priorityQueue.enqueue('Jack', 1)
priorityQueue.enqueue('Camila', 1)
priorityQueue.enqueue('Surmon', 3)
priorityQueue.enqueue('skyRover', 2)
priorityQueue.enqueue('司马萌', 1)
priorityQueue.print()
console.log(priorityQueue.isEmpty, priorityQueue.size) // false 6
循环队列
为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表、队列的方式来在实际编程应用中来实现。
下面我们基于首次实现的队列类，简单实现一个循环引用的示例：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
class LoopQueue extends Queue {
constructor(items) {
super(items)
}
getIndex(index) {
const length = this.items.length
return index > length ? (index % length) : index
}
find(index) {
return !this.isEmpty ? this.items[this.getIndex(index)] : null
}
}
访问一个循环队列：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
const loopQueue = new LoopQueue(['Surmon'])
loopQueue.enqueue('SkyRover')
loopQueue.enqueue('Even')
loopQueue.enqueue('Alice')
console.log(loopQueue.size, loopQueue.isEmpty) // 4 false
console.log(loopQueue.find(26)) // 'Evan'
console.log(loopQueue.find(87651)) // 'Alice'
链表
要存储多个元素，数组（或列表）可能是最常用的数据结构。
每种语言都实现了数组。这种数据结构非常方便，提供了一个便利的[]语法来访问它的元素。
然而，这种数据结构有一个缺点：在大多数语言中，数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素；
尽管 JavaScript 中的Array类方法可以帮我们做这些事，但背后的处理机制同样如此。
链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。下图展示了链表的结构:
相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。
数组的另一个细节是可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，需要从起点(表头)开始迭代列表直到找到所需的元素。
现实中有许多链表的例子：一列火车是由一系列车厢/车皮组成的，每节车厢/车皮都相互连接，你很容易分离一节车皮，改变它的位置，添加或移除它。下图演示了一列火车，每节车皮都是列表的元素，车皮间的连接就是指针：
下面我们使用 Javascript 创建一个链表类：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
// 链表节点
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
// 链表
class LinkedList {
constructor() {
this.head = null
this.length = 0
}
// 追加元素
append(element) {
const node = new Node(element)
let current = null
if (this.head === null) {
this.head = node
} else {
current = this.head
while(current.next) {
current = current.next
}
current.next = node
}
this.length++
}
// 任意位置插入元素
insert(position, element) {
if (position >= 0 && position <= this.length) {
const node = new Node(element)
let current = this.head
let previous = null
let index = 0
if (position === 0) {
this.head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
this.length++
return true
}
return false
}
// 移除指定位置元素
removeAt(position) {
// 检查越界值
if (position > -1 && position < length) {
let current = this.head
let previous = null
let index = 0
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element
}
return null
}
// 寻找元素下标
findIndex(element) {
let current = this.head
let index = -1
while (current) {
if (element === current.element) {
return index + 1
}
index++
current = current.next
}
return -1
}
// 删除指定文档
remove(element) {
const index = this.indexOf(element)
return this.removeAt(index)
}
isEmpty() {
return !this.length
}
size() {
return this.length
}
// 转为字符串
toString() {
let current = this.head
let string = ''
while (current) {
string += ` ${current.element}`
current = current.next
}
return string
}
}
链表类的使用：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
const linkedList = new LinkedList()
console.log(linkedList)
linkedList.append(2)
linkedList.append(6)
linkedList.append(24)
linkedList.append(152)
linkedList.insert(3, 18)
console.log(linkedList)
console.log(linkedList.findIndex(24))
双向链表
链表有多种不同的类型，这一节介绍双向链表。双向链表和普通链表的区别在于，在链表中， 一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的:一个链向下一个元素， 另一个链向前一个元素，如下图所示:
双向链表提供了两种迭代列表的方法:从头到尾，或者反过来。我们也可以访问一个特定节 点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表 起点，重新开始迭代。这是双向链表的一个优点。
我们继续来实现一个双向链表类：
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
// 链表节点
class Node {
constructor(element) {
this.element = element
this.prev = null
this.next = null
}
}
// 双向链表
class DoublyLinkedList {
constructor() {
this.head = null
this.tail = null
this.length = 0
}
// 任意位置插入元素
insert(position, element) {
if (position >= 0 && position <= this.length){
const node = new Node(element)
let current = this.head
let previous = null
let index = 0
// 首位
if (position === 0) {
if (!head){
this.head = node
this.tail = node
} else {
node.next = current
this.head = node
current.prev = node
}
// 末位
} else if (position === this.length) {
current = this.tail
current.next = node
node.prev = current
this.tail = node
// 中位
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
current.prev = node
node.prev = previous
}
this.length++
return true
}
return false
}
// 移除指定位置元素
removeAt(position) {
if (position > -1 && position < this.length) {
let current = this.head
let previous = null
let index = 0
// 首位
if (position === 0) {
this.head = this.head.next
this.head.prev = null
if (this.length === 1) {
this.tail = null
}
// 末位
} else if (position === this.length - 1) {
this.tail = this.tail.prev
this.tail.next = null
// 中位
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
current.next.prev = previous
}
this.length--
return current.element
} else {
return null
}
}
// 其他方法...
}
循环链表
循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针(tail.next)不是引用null， 而是指向第一个元素(head)，如下图所示。
双向循环链表有指向head元素的tail.next，和指向tail元素的head.prev。
链表相比数组最重要的优点，那就是无需移动链表中的元素，就能轻松地添加和移除元素。因此，当你需要添加和移除很多元素 时，最好的选择就是链表，而非数组。
😃😃😃
BUG测试💊
代理评论测试💊
回复 #259 @jooger ：
测你大爷
回复 #261 @Surmon ：
😜
有个地方写错了：后序遍历：左侧子节点 => 右侧子节点 => 节点本身
你手机端的说说广播📢会导致文章列表重绘，一直抖。可以点点上下箭头shi shi
回复 #264 @zangxd ：
谢谢，实际上这篇文章还没彻底整理好...🌹🌹🌹
回复 #265 @幾米 ：
🌻🌻🌻谢谢
回复 #267 @Surmon ：
看错了，是轮播图导致的。评论的表单，iPhone 的输入法有自动补全提示，自动填入之后，你的验证不能通过。你去看看 input 的 compositionstart 和 compositionend 事件。不知道什么原因，我Safari访问，如果不打开vpn，提示无法连接到服务器😂
哥，看你的文章一下午，听了一下午歌，发现了 京东热，是不是罪过啊
回复 #310 @like ：
东京到底热不热
回复 #311 @Surmon ：
很躁😂，哈哈
😍
请问博主，本网站web端，可以加一个放宽文章页面的按钮吗，好窄
🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏🙏💪
回复 #377 @zgj233 ：
好主意，很快加上
回复 #378 @Surmon ：
哈哈哈， 匿名聊天真开心。请问用户的头像能设置么？
回复 #379 @zgj233 ：
gravatar
回复 #377 @zgj233 ：
加上了
回复 #389 @Surmon ：
感谢博主加上全屏浏览的功能， 看文章更方便了
回复 #465 @zgj233 ：
🌹
博主好强 👍👍👍 向你学习
创建图类的时候不需要加 （）吧
class Graph {}我想请教一下哈，为什么数组前面加个；就不会导致报错呢 😃
回复 #539 @lihaozecq ：
看这里： JavaScript 语句后应该加分号么？ - 尤雨溪的回答 - 知乎 https://www.zhihu.com/question/20298345/answer/49551142
可以可以
好
能不能把背景的canvas去掉，好卡
回复 #812 @kyle ：
左下角有开关啊
看完了，收货良多呀！ 非常感谢 👍