JavaScript 算法与数据结构

认真学习 JavaScript 数据结构

准备工作

比较器

一个比较器类拥有以下方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 类接收一个可选的比较函数作为参数
compare: (a, b) => number
// 判断两个参数是否相等
equal: (a: (number | string), b: (number | string)) => boolean
// 判断a是否小于b
lessThan: (a: (number | string), b: (number | string)) => boolean
// 判断a是否大于b
greaterThan: (a: (number | string), b: (number | string)) => boolean
// 判断a是否小于等于b
lessThanOrEqual: (a: (number | string), b: (number | string)) => boolean
// 判断a是否大于等于b
greaterThanOrEqual: (a: (number | string), b: (number | string)) => boolean
// 反转比较函数的两个参数即从a,b转换为b,a
reverse: () => void

构造一个这样的比较器函数之后可以在后面的数据结构中进行使用

链表

在计算机科学中,链表是数据元素的线性集合,其中每个元素的顺序并不是由它们在内存中的物理位置给出的,而是每个元素都持有下一个元素的指针,它是一组节点组成的数据结构,这些节点一起表示序列,在最简单的形式下,每个节点由数据到序列中下一个节点的引用组成的,这种结构允许在迭代的时候在任意位置有效的插入或者移除元素,更复杂的变体添加了额外的连接,允许有效插入或从任意元素引用删除,列表的缺点是访问时间是线性的(O(n),并且无法优化),例如数组的随机访问,在链表中是不可行的,与链表相比,数组局域更好的缓存局部性.

Linked List

其支持一下几种主要的方法:

  • 插入
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

/**
* 这个插入节点非常有趣
*/
append(value: any): LinkedListInterface {

// 首先根据参数生成一个节点这里假设 value = 1
// 那么生成的节点就是 {value:1, next: null}
const newNode = new LinkedListNode(value)
// 假如一开始链表是空的
if (!this.head) {
// 那么头节点和尾节点指向的是同一个对象 this.head = {value:1, next: null}
// this.tail = {value: 1, next: null} 注意这里引用的是同一个对象
this.head = newNode
this.tail = newNode
return this
}


// 那么第二次添加节点链表头结点不为空执行下面的赋值 这里假设 value参数为2
// 首先this.tail.netx = {value:2,next:null}
// 那么this.tail 完整储存的内容就是 {value:1, next: {value:2,next:null}}
// 因为this.head 和 this.tail 指向的是同一个对象所以完整的的链表是这样的
// this.head的值 {value:1, next: {value:2,next:null}}
// this.tail的值 {value:1, next: {value:2,next:null}}
this.tail.next = newNode

// 接下来将tali 赋值为 {value: 2, next:null}
// 此时链表结构为
// this.head = {value:1, next: {value:2,next:null}}
// this.tail = {value: 2, next:null}
// 这里this.head.next引用的对象和tail引用的对象是同一个对象
// 所以下次赋值会重复这个过程,即最后一个节点和tail节点引用的是同一个对象
// 所以重复
// this.tail.next = newNode
// this.tail = newNode
// 即可完成添加新的节点
this.tail = newNode

return this

}
  • 搜索
  • 删除
  • 反转
  • 反向遍历

复杂度

时间复杂度

类型访问搜索插入删除
列表O(n)O(n)O(1)O(1)
数组O(1)O(n)O(n)O(n)

空间复杂度

O(n)

双向链表

在计算机科学中,双向链表是一种线性数据结构,由一组被称为节点的顺序连接记录组成,每个节点包含两个字段,称为链接,节点中有上一个节点和下一个节点的引用,可以被概念化为由两个相同数据形成的两个链表,但是以相反的顺序组成

Doubly Linked List

构成双向链表的基本方法

  • insert
  • delte
  • reverse traversal

相关复杂度

Access(访问)Searchinsertindeleteion
O(n)O(n)O(1)O(1)

空间复杂度

O(n)

笔记

双向链表顾名思义,就是每个节点都由三个部分组成

  • 上个节点的引用
  • 下个节点的引用
  • 节点存储的值

prepend

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
/** 向节点头部插入值 */
prepened(value: any): DoublyLinkedListInterface {

// 生成节点
const newNode = new DoublyLinkedListNode(value)

// 如果头结点存在值那么就给它的pervious节点赋值

// 使用实际值来带入比较好理解
// 假设链表为空,第一次插入值,并且假设值为1
// 那么就是hand 和 tali 节点指向同一个对象值都为{value:1,next:null,previous:null}
// 第二次调用该方法传入一个假设值为2
// 首先hand不为空则对pervious进行赋值,由于hand tali指向的是同一个对象那么赋值之后
// this.hand: {value:1, next: null, pervious: {value:1, next: null, previous: null}}
// this.tali: {value:1, next: null, pervious: {value:1, next: null, previous: null}}
// 然后修改hand的值为 {value:1, next: null, previous: null}
// 这样 this.hand: {value:1, next: null, previous: null}
// this.tali : {value:1, next: null, pervious: {value:1, next: null, previous: null}}
// 从而实现向链表头部添加了一个节点
if (this.hand) {
this.hand.pervious = newNode
}
this.hand = newNode

if (!this.tail) {
this.tail = newNode
}

return this

}

其他的方面和单向链表差不多,写完之后代码测试就错了三处,可喜可贺