在 Part 1中,我们仔细研究了链接列表是什么,为什么它们需要创建更先进的数据结构,现在我们可以学习如何在JavaScript中开始实施一个功能齐全的双链接列表。
单独链接的列表和其他数据结构中的实现通常只会是我们这里所涵盖的更多版本,所以这将是一个很好的参考。
结构
和任何其他类一样,我们可以在每个节点中存储我们想要的任何东西,唯一重要的部分是下一步和预先指针,默认情况下应该是零。
同样,我们列表所需要的唯一东西是它的尾巴,头部和长度。我们将需要手动操纵长度,因为与数组不同,它不会被计算给我们,并且需要搜索项目。
1class Node {
2 constructor(val) {
3 this.val = val;
4 this.next = null;
5 this.prev = null;
6 };
7};
8
9class linkedList {
10 constructor() {
11 this.head = null;
12 this.tail = null;
13 this.length = 0;
14 };
15};
创造
现在我们可以开始在我们的链接列表类内设置所有方法,因为我们没有任何像推或改变这样的正常好处,我们将不得不创建自己的版本。
头和尾巴
我们的大多数操作都更多地基于在周围节点中操纵指针,而不是在我们想要更改的项目上添加一些东西,不仅仅是将新节点推到我们想要的位置,就像在一个数组上一样,而是更改前或之后的项目上的指针,指向我们的新项目,然后手动增加列表的长度。
如果列表中没有任何东西,我们希望将新项目设置为头和尾巴,因为它是唯一的项目. 要从列表的末尾添加或删除,我们将取代我们想要的当前头/尾巴,并将其指针设置为我们的新项目或零,将列表的头/尾巴更改为我们的新节点或零,然后增加长度。
1addHead(val) {
2 let newNode = new Node(val);
3
4 if (!this.head) {
5 this.head = newNode;
6 this.tail = this.head;
7 };
8
9 this.head.prev = newNode;
10 newNode.next = this.head;
11 this.head = newNode;
12
13 this.length++;
14 return this;
15}
16
17addTail(val) {
18 let newNode = new Node(val);
19
20 if (!this.head) {
21 this.head = newNode;
22 this.tail = newNode;
23 };
24
25 this.tail.next = newNode;
26 newNode.prev = this.tail;
27 this.tail = newNode;
28
29 this.length++;
30 return this;
31}
32
33removeHead() {
34 let removed = this.head;
35 if (!this.head) return undefined;
36
37 this.head = this.head.next;
38 this.head.prev = null;
39
40 this.length--;
41 return removed;
42}
43
44removeTail() {
45 let removed = this.tail;
46 if (!this.tail) return undefined;
47
48 if (this.length === 1) {
49 this.head = null;
50 this.tail = null;
51 };
52
53 this.tail = removed.prev;
54 this.tail.next = null;
55
56 this.length--;
57 return removed;
58}
找到
由于我们没有索引来获取我们的项目,我们将在列表中间插入/删除一些问题,所以我们将需要自己的实用功能。
它非常简单,我们只需要存储当前的项目,并使用为或而循环使用我们的指针来更新当前,直到我们到达我们想要的项目。
图形 / 动画 通过 VisuAlgo.net
当然,这给了我们一个O(n)搜索时间,但由于我们使用了一个双链接的列表,我们可以从尾巴开始,如果我们想要的东西是在列表的中间,给了我们O(n / 2)。
1find(index) {
2 let current
3 if (index < 0 || index >= this.length) return undefined;
4
5 if (index <= this.length / 2) {
6 current = this.head;
7 for (let i = 0; i < index; i++) current = current.next;
8 } else {
9 current = this.tail;
10 for (let i = this.length; i > index; i--) current = current.prev;
11 }
12
13 return current;
14}
插入和删除
现在我们已经有了我们的小实用程序,我们可以用它来找到我们想要的索引中的项目,然后将指针设置在它的前面和后面的项目到我们的新节点上,从而将其粘贴到位。
图形 / 动画 通过 VisuAlgo.net
如果指数位于头部或尾巴上,我们可以简单地重复使用以前的方法。
1insert(val, index) {
2 if (index < 0 || index > this.length) return null;
3 if (index === this.length) return this.addTail(val);
4 if (index === 0) return this.addHead(val);
5
6 let prev = this.find(index - 1),
7 newNode = new Node(val),
8 temp = prev.next;
9
10 prev.next = newNode;
11 newNode.next = temp;
12 newNode.prev = prev;
13
14 this.length++;
15 return true;
16}
删除显然只是插入的反面,稍微简单一些. 找到我们想要删除的节点,并将周围节点上的指针放在彼此旁边,没有留下任何引用删除节点的内容。
图形 / 动画 通过 VisuAlgo.net
1remove(index) {
2 if (index < 0 || index >= this.length) return null;
3 if (index === this.length) return this.removeTail();
4 if (index === 0) return this.removeHead();
5
6 let removed = this.find(index);
7
8 removed.prev.next = removed.next;
9 removed.next.prev = removed.prev;
10
11 this.length--;
12 return removed;
13}
更新
这个很简单,几乎不值得提到,只需找到该项目并重置其值。
1update(val, index) {
2 let node = this.find(index);
3 if (node) node.val = val;
4 return node;
5}
结论
虽然这可能看起来像是一个很大的工作,但要记住,在许多情况下,你不需要所有的。
我真的建议检查 Buckets.js 当你不想手动创建一个时,尽管理解这个概念在更深层次上总是很好的。