<EricWXY/>
Javascript 线性数据结构学习总结(较长)
ericwxy
  2022-03-06 21:23:57   2024-02-28 12:59:47

又是一个阳光明媚的周末，在结束了一周的工作（和周六“福报”）之后对换新工作后的这两周做一个简单的总结。首先第一点，园区食堂还是不错的。给我的感觉像是回到了大学的生活，每天排队吃饭排队领宵夜。还有就是我已经很久没有这种每天早上坐下来享受一份热气腾腾早饭和《朝闻天下》的感觉了。工作上呢目前也算开始可以上手用 angular 写项目了并且还用 rxjs 实现了一些简单的响应式编程的功能，虽然还有很大的进步空间。为了之后的”专业级”考试我最近也在集中巩固“算法数据结构”最近也算是又有了一些新的感悟。总体上来说虽然每天通勤会有些辛苦但是每天强制早起看书也是不错的，工作的环境那也是没得说也还是有很多需要学需要自我提升的。
在下午出去晒了晒太阳之后,我决定对这一周算法数据结构上面学习做一个总结。

线性数据结构

先来给出一个我对于线性数据结构的定义和理解吧。线性结构是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。我理解中 Javascript 中可以接触到的线性数据结构大体上有这么几种：数组、栈、队列、链表。下面我就分别对这几种数据结构做一个总结。

数组

首先数组应该是我们平时 JS 开发接触最多的线性数据结构了吧,而且我们也不用自己去实现什么因为 JS 原生提供的方法已经足够我们用的了。数组的核心方法大体上可以分成两类：1.元素操作类(push、pop、shift、unshift、splice 等)2.迭代器类(forEach、map、filter、reduce、every、some 等)。当然了还有一些其他操作如合并排序之类的。其实关于数组没有什么特别的点，我个人觉得吧我们需要注意的就是关于数组元素操作带来的下标移动（上一篇已经说过）。

栈

下面要开始聊一些 JS 自身没有的数据结构了。先从栈开始, 栈也是我们经常会接触到的一种数据结构了，比如我们 JS 聊到原理时经常会提到的 callStack （调用栈）。我们在 JS 中实现栈(LIFO)有很多方式,比如最常见也是最方便的就是用数组去模拟。

1
2
3
4
5
6
7
8
9
function Stack() {
  this.stack = [];
}
Stack.prototype.push = function (item) {
  this.stack.push(item);
};
Stack.prototype.pop = function () {
  return stack.pop();
};

应该稍微了解一点数据结构的前端开发者都因该用的是数组的方式去实现。但是呢，数组实现的方式它方便它不一定性能就最好。我们知道数组的很多操作的实践复杂度是 O(n),而且其实栈并不在意下标也不会直接去取中间的某一个元素。所以我们利用 Object 或这链表去实现 Stack 类或许会更好。

基于 Object 实现的 Stack 类

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
class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }

  push(item) {
    this.items[this.count] = item;
    this.count++;
  }

  pop() {
    if (this.isEmpty()) return void 0;
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return void 0;
    }
    return this.items[this.count - 1];
  }

  get size() {
    return this.count;
  }

  isEmpty() {
    return this.count === 0;
  }

  clear() {
    this.items = {};
    this.count = 0;
  }

  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

保护数据结构内部元素

两种方案：1.可以使用 Symbol 2.利用 WeakMap

下面来记录一下利用 WeekMap 来保护内部元素的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const items = new WeekMap();
class Stack {
  constructor() {
    items.set(this, []);
  }

  push(item) {
    const _items = items.get(this);
    _items.push(item);
  }

  pop() {
    const _items = items.get(this);
    return _items.pop();
  }
  // 其他方法
}

基于链表实现的 Stack 类

上一篇也写到了利用链表来实现 Queue 类，链表可以实现队列当然也可以实现栈喽。后面的双向链表会具体实现。

用栈解决的问题

上面也提到了 JS 中的 callStack 就是一种栈的结构，栈在实际的应用也是很广泛的。我们可以用它来存储访问过的路径、撤销的操作，或者可以用它解决进制转换的问题或者用来解决一个经典的括号匹配的问题。

队列

队列与栈非常相似，队列区别于栈的最大特征为（FIFO）先进先出。听过 callStack 的开发者一定也听过一个叫 callbackQueue 的东西。在我之前做过的项目中我也利用这个数据结构来做过一个消息去重复的 messageQueue。

跟栈一样 JS 中也是没有原生支持的，我们需要自己实现。实现方式也是多种多样，首先最方便最简单的还是数组(push/shift 或 unshift/pop)。还是那个问题，下标移动会导致一定的性能问题。所以我们可以用 Object 来实现。

基于 Object 实现的 Queue 类

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
class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  // 入队列
  enqueue(item) {
    this.items[this.count] = item;
    this.count++;
  }

  // 出队列
  dequeue() {
    if (this.isEmpty()) return void 0;
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

  // 取队头元素
  peek() {
    if (this.isEmpty()) return void 0;
    return this.items[this.lowestCount];
  }

  // 队长度
  get size() {
    return this.count - this.lowestCount;
  }

  isEmpty() {
    return this.count - this.lowestCount === 0;
  }

  clear() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  toString() {
    if (this.isEmpty()) return "";
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

从上面的代码也可以看出用 Object 来实现的队列并不会取关注下标（因为下标是否从零开始并不那么重要），出入队列的操作也不会取操作下标。这就是为什么这样比用数组实现的性能好的原因。

双端队列

顾名思义 元素的流动可以是双向的。

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
class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  addFront(item) {
    if (this.isEmpty()) this.addBack(item);
    else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = item;
    } else {
      // 这里就可以看到类似数组unshift时数组内部的操作了
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = item;
    }
  }

  // 其他方法 （addBack、removeFront、removeBack、peekFront、peekBack ...)
}

使用双端队列

前几天复习一个回文数问题我又就运用双端队列的新思路

1
2
3
4
5
6
7
8
9
10
11
12
13
function isPalindrome(x: number): boolean {
  const deque = x.toString().split("");
  let flag = true;
  while (deque.length > 1) {
    const head = deque.shift();
    const tail = deque.pop();
    if (head !== tail) {
      flag = false;
      return flag;
    }
  }
  return flag;
}

链表

前端开发者应该都了解原型链，其实它就可以理解成一个链表(只不过原型链中的 next 不叫 next 叫做 prototype)。其实我觉链表应该放在栈和队列前面总结，因为队列和栈都可以用链表来实现。废话不多说先来实现。

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
import { defaultEquals } from "./utils";
import { Node } from "./models/linked-list-models";

export default class LinkedList {
  constructor(equalsFn = defaultEquals) {
    this.count = 0;
    this.head = null;
    this.equalsFn = equalsFn;
  }

  push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.head;
      while (current.next != null) {
        current = current.next;
      }
      current.next = node;
    }
    this.count++;
  }

  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        const current = previous.next;
        node.next = current;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

  removeAt(index) {
    // 检查越界
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return void 0;
  }

  remove(element) {
    const index = this.indexOf(element);
    return this.removeAt(index);
  }

  getElementAt(index) {
    if (index >= 0 && index <= this.count) {
      let node = this.head;
      for (let i = 0; i < index && node != null; i++) {
        node = node.next;
      }
      return node;
    }
    return void 0;
  }

  indexOf(element) {
    let current = this.head;
    for (let i = 0; i < this.count && current != null; i++) {
      if (this.equalsFn(element, current.element)) {
        return i;
      }
      current = current.next;
    }
    return -1;
  }

  get size() {
    return this.count;
  }

  isEmpty() {
    return this.size === 0;
  }

  toString() {
    if (this.head == null) return "";
    let str = `${this.head.element}`;
    let current = this.head.next;
    for (let i = 1; i < this.size && current != null; i++) {
      str = `${str},${current.element}`;
      current = current.next;
    }
    return str;
  }
}

来几个常见的链表问题

  • 链表遍历
1
2
3
4
5
let p = a;
while (p) {
  console.log(p.val);
  p = p.next;
}
  • 手写一个 instanceOf (思路类似链表遍历)
1
2
3
4
5
6
7
8
9
10
11
// 判断 param1 是否在 param2 的原型链上
function instanceOf(param1, param2) {
  let p = param1;
  while (p) {
    if (p.__proto__ === param2.prototype) {
      return true;
    }
    p = p.__proto__;
  }
  return false;
}
  • 判断回文链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isPalindrome(head) {
  const stack = [];
  let p = head;
  while (p) {
    stack.push(p);
    p = p.next;
  }
  while (stack.length !== 0) {
    if (head.val !== stack.pop().val) {
      return false;
    }
    head = head.next;
  }
  return true;
}
  • 反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let p1 = head;
  let p2 = null;
  while (p1) {
    const tmp = p1.next;
    p1.next = p2;
    p2 = p1;
    p1 = tmp;
  }
  return p2;
};
  • 从尾到头打印链表
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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reversePrint(head: ListNode | null): number[] {
  // 方法1：遍历链表推入数组（利用数组反向输出 - unshift 或者 reverse）
  // let p: ListNode | null = head; // 遍历链表指针
  // const result: number[] = [];
  // // 遍历链表并将值推入数组
  // while (p) {
  //   result.unshift(p.val);
  //   p = p.next;
  // }
  // // return 结果数组反序
  // return result;

  // 方法2：反转链表 输出
  // let p: ListNode | null = head;
  // let p2: ListNode | null = null;
  // // 反转链表
  // while (p) {
  //     const tmp = p.next;
  //     p.next = p2;
  //     p2 = p;
  //     p = tmp;
  // }
  // const result: number[] = [];
  // while (p2) {
  //     result.push(p2.val);
  //     p2 = p2.next;
  // }
  // return result;

  // 方法3：利用栈
  // const stack = [];
  // let p: ListNode | null = head; // 遍历链表指针

  // while (p) {
  //   stack.push(p.val);
  //   p = p.next;
  // }
  // const result = [];
  // while (stack.length) {
  //   result.push(stack.pop());
  // }
  // return result;

  // 方法4：利用递归（callStack）
  const result: number[] = [];
  const pushItem = (node: ListNode | null) => {
    if (node != null) {
      if (node.next != null) pushItem(node.next);
      result.push(node.val);
    }
  };
  pushItem(head);
  return result;
}

上面这个反向打印链表是《剑指 Offer》中的一个问题，可以看到我用了四种思路。

还有 双向链表、循环链表、有序链表 等衍生的类型 今天实在肝不动了。。。 下一期吧。

写在最后

本来想要一次把最近学习的线性数据结构总结完的可是今天已经写到很晚了（破涕为笑）。我下周再来更新剩下的部分。下周除了继续精进 angular 本且坚持刷题以外，重点来总结一下各种排序算法。就这样吧，继续加油。

 评论
评论插件加载失败
正在加载评论插件