JavaScript 数据结构：双向链表：向末尾添加数据
引言
上次，我们学习了如何建立双向链表。
今天，我们将学习如何将一个新节点推入双向链表的末尾。
启动代码
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
}
想法
首先，我们应该考虑一下限制因素和可能性：
如果列表为空：
- 创建一个新节点
- 新节点应该成为头部和尾部。
- 将列表长度增加 1
- 返回新节点
其余所有案例：
- 创建一个新节点
- 当前尾部应指向前方（=下一个）新节点
- 新节点应该指向（= prev）当前尾部
- 新节点应该成为新的尾部
- 将列表长度增加 1
- 返回新节点
示例：空列表
- 当前列表：为空（无头尾）
- 所需列表：A（头部和尾部）
示例 2：包含 1 个节点的列表
- 当前列表：A（头部和尾部）
- 期望列表：A（头部）<===> B（尾部）
步骤：
- 当前列表：A（头部和尾部）
- 期望列表：A（头部）<===> B（尾部）
the current tail should point forward (= next) to the new node：A（头部和尾部）=> Bthe new node should point back (= prev) to the current tail：A（头部和尾部）<===> Bthe new node should become the new tailA（头部）<===> B（尾部）
=> 最后一步后的列表与所需列表一致
执行
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.length = 0;
this.head = null;
this.tail = null;
}
push(value) {
// create a new node
const newNode = new Node(value);
// if the list is empty,the new node should become the head and the tail
if (!this.length) {
this.head = newNode;
this.tail = newNode;
} else {
// the current tail should point forward (= next) to the new node
this.tail.next = newNode;
// the new node should point back (= prev) to the current tail
newNode.prev = this.tail;
// the new node should become the new tail
this.tail = newNode;
}
// increase length by 1
this.length += 1;
// return new node
return newNode;
}
}
结果
让我们来看看如何使用双向链表的push方法及其结果。
// empty list
const newDLL = new DoublyLinkedList();
console.log(newDLL);
// DoublyLinkedList { length: 0, head: null, tail: null }
// push first new node
console.log(newDLL.push("new node 1"));
// Node { value: 'new node 1', prev: null, next: null }
console.log(newDLL);
// DoublyLinkedList {
// length: 1,
// head: Node { value: 'new node 1', prev: null, next: null },
// tail: Node { value: 'new node 1', prev: null, next: null }
// }
// push second new node
console.log(newDLL.push("new node 2"));
// <ref *1> Node {
// value: 'new node 2',
// prev: Node { value: 'new node 1', prev: null, next: [Circular *1] },
// next: null
// }
console.log(newDLL);
// DoublyLinkedList {
// length: 2,
// head: <ref *1> Node {
// value: 'new node 1',
// prev: null,
// next: Node { value: 'new node 2', prev: [Circular *1], next: null }
// },
// tail: <ref *2> Node {
// value: 'new node 2',
// prev: <ref *1> Node {
// value: 'new node 1',
// prev: null,
// next: [Circular *2]
// },
// next: null
// }
// }
下一部分
我们将实现双向链表的下一个方法：pop/ 从末尾删除一个节点。
想要收到通知，请订阅！
任务
- 你从结果中发现了什么新东西吗？
- 它们是什么意思？