我正在用 javascript 构建链接列表。 我有一部分不明白。
function Node(element) {
this.element = element;
this.next = null;
this.previous = null;
}
function LList() {
this.head = new Node("head");
this.find = find;
this.findLast = findLast;
this.remove = remove;
this.insert = insert;
this.display = display;
this.dispReverse = dispReverse;
}
function find(item) {
var currNode = this.head;
while(currNode.element != item) {
currNode = currNode.next;
}
return currNode;
}
function display(list) {
var currNode = this.head.next;
while (currNode != null) {
console.log(currNode.element);
currNode = currNode.next;
}
}
function insert(newElement, item) {
var newNode = new Node(newElement);
var current = this.find(item);
newNode.next = current.next;
newNode.previous = current;
current.next = newNode;
// Why I dont need this part?
// Since new node got inserted, on my thoughts,
// the next node of the current node should point the new node as a previous one
// current.next.previous = newNode;
}
function remove(item) {
var currNode = this.find(item);
if (currNode.next != null) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
function findLast() {
var currNode = this.head;
while (currNode.next != null) {
currNode = currNode.next;
}
return currNode;
}
function dispReverse() {
var currNode = this.head;
currNode = this.findLast();
while(currNode.previous != null) {
console.log(currNode.element);
currNode = currNode.previous;
}
}
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Carlisle", "Russellville");
cities.insert("Alma", "Carlisle");
cities.display();
cities.remove("Carlisle");
cities.display();
cities.dispReverse();
/*
Output should look like this:
Conway
Russellville
Carlisle
Alma
Conway
Russellville
Alma
Alma
Russellville
Conway
*/
问题是插入函数!
假设我已经有 A B C 节点。
我想在B后面插入K。
目前,B 的下一个和上一个分别是 C 和 A。
C的前一个元素是B。
一旦我把K放在B后面,
A B K C
(1) K 的下一个元素将是 C
(2) K 的前一个元素将是 B。
(3) B的下一个元素是K
(4) C的前一个元素是K。
在我在Insert函数中编写的代码中,下面的每一行代码都应该处理上面的语句。
(1) newNode.next = current.next;
(2) newNode.previous = 当前;
(3) current.next = newNode;
(4) current.next.previous = newNode;
但是当我运行包括(4)在内的整个代码时,发生了错误。
我不明白为什么...
没有(4)行代码,它就可以工作。
有谁可以帮助我理解这一点吗?
最佳答案
您需要在步骤 3 之前执行步骤 4:
current.next.previous = newNode
current.next = newNode
事实上,在查找“旧”current 之前,
的 current.next
(C) 的引用被设置为 newNode
(K)。 nextprevious
属性(指向 B 时为 current.next.previous
)。一旦为当前节点分配了新值,您对当前节点的引用就会更改。这就是为什么 current.next.previous
实际上返回 newNode.previous
而不是您期望的节点引用。
关于javascript - javascript中的双向链表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31284954/