javascript - 双链表中交换节点会导致无限递归

Question

我有以下节点构造函数:

const Node = function(data){
  this.data = data
  this.next = null
  this.previous = null
}

在我的 LinkedList 构造函数中使用:

const LinkedList = function(){
  this.head = new Node('head')
}

我可以使用以下方法插入节点:

LinkedList.prototype.insert = function(item,after){
  const newNode = new Node(item)
  const curr = after ? this.find(after) : this.head
  newNode.next = curr.next
  newNode.previous = curr
  curr.next = newNode
}

其中 find 方法是:

LinkedList.prototype.find = function(item){
  let currentNode = this.head
  while(currentNode && currentNode.data !== item){
    currentNode = currentNode.next
  }
  return currentNode
}

并且可以使用以下方法将项目作为数组查看:

LinkedList.prototype.toArray = function(){
  const arr = []
  let currItem = this.head.next
  while(currItem){
    arr.push(currItem.data)
    currItem = currItem.next
  }
  return arr
}

我现在的问题是我正在尝试在 LinkedList 上实现一个 switch 函数，我可以在其中传递两个值并切换它们在列表中的位置。下面是我所拥有的，它似乎适用于彼此不相邻的项目:

LinkedList.prototype.switch = function(a,b){
  const aNode = this.find(a),
        bNode = this.find(b)
  if(!aNode || !bNode){
    throw new Error('Both nodes were not inside of the list')
  }
  const aNext = aNode.next,
        aPrevious = aNode.previous,
        bNext = bNode.next,
        bPrevious = bNode.previous

  aNode.next = bNext
  aNode.previous = bPrevious
  aNode.previous.next = aNode

  bNode.next = aNext
  bNode.previous = aPrevious
  bNode.previous.next = bNode

}

我想知道我在这里做错了什么，导致当我交换彼此相邻的元素时，我的计算机陷入无限递归。例如，以下代码行有效:

const list = new LinkedList()
list.insert(1)
list.insert(2,1)
list.insert(3,2)
list.switch(1,3)
list.toArray() // [3,2,1]

但是如果我有以下代码，它

const list = new LinkedList()
list.insert(1)
list.insert(2,1)
list.switch(1,2)
list.toArray() // crashes terminal

我知道这是我的 switch 方法中的一个愚蠢的逻辑错误，但我一生都无法弄清楚是什么。

Answer 1

我看到的问题出在你的插入函数中。如果您有一个包含两个项目的链接列表，并且您调用 insert('New Node', null)，您的列表如下所示:

您仍然需要将前一个指针设置为新节点，如下所示:

LinkedList.prototype.insert = function(item,after){
  const newNode = new Node(item);
  const curr = after ? this.find(after) : this.head;
  newNode.next = curr.next;
  curr.next.previous = newNode; <----- This is the extra line
  newNode.previous = curr;
  curr.next = newNode;
}