javascript 中的双向链表

Question

我在 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 = 新节点；
(4) current.next.previous = newNode;

但是当我运行包括(4)在内的整个代码时，发生了错误。
我不明白为什么...
没有第 (4) 行代码，它可以工作。

有谁能帮我理解一下吗？

Answer 1

最后一行的插入逻辑似乎有误：

current.next = 新节点；

current.next.previous = newNode;

这实际上意味着

newNode.previous=新节点；

因为您在第 3 条语句中将 current.next 的值设置为 newNode

应该是：

newNode.next.previous = newNode.

Answer 2

您需要在第 3 步之前执行第 4 步：

current.next.previous = newNode
current.next = newNode

事实上，current.next (C) 的引用在您查找 "old" current.next 的 previous 属性（ current.next.previous 当指向 B 时）。一旦您为其分配新值，您对当前节点的引用就会更改。这就是 current.next.previous 实际上返回 newNode.previous 而不是您期望的节点引用的原因。

javascript 中的双向链表

Doubly Linked List in javascript

javascript

data-structures

linked-list

doubly-linked-list