删除对双链接链表中已删除节点的引用

Question

我可以成功删除我的双链表中的一个节点，但我的node.next仍然"指向"已删除的节点，而旧节点的prev仍然"指向"已删除节点。当我打印列表时，节点不在那里，当调用findNode((时，返回的结果与预期的一样("没有具有该值的节点"(

这是我的课：

class Node {
constructor(value = null) {
this.value = value;
this.next = null;
this.prev = null;
}
}
class LinkedList {
constructor() {
this.head = null
this.tail = this.head
this.size = 0
}
findNode(value) {
let node = this.head
while(node !== null && node.value !== null) {
node = node.next
}
return node !== null
}
remove(value) {
let node = this.head
while(node.next !== null) {
if(node.value === value) {
const newCurrentNode = node.prev
const newNextNode = node.next
newCurrentNode.next = newNextNode
newNextNode.prev = newCurrentNode
}
node = node.next
if(node.next === null) {
return 'node node with that value'
}
}
this.size--
return this.print()
}
removeAtIndex(position) {
let node = this.head
if(position < 1) this.removeHead(value)
if(position > this.size) return 'no node at that position'
let count = 0
while(count !== position){
console.log(`${count} is not at position`)
node = node.next
count++
}
// console.log(`${count} is at position`)
const prevNode = node.prev
const newNextNode = node.next
prevNode.next = newNextNode
newNextNode.prev = prevNode
node.next = null
node.prev = null
this.size--
return this.print() // change to return this for LL
}
insertNewHead(value) {
const newHead = new Node(value)
const oldHead = this.head
if(!this.head) {
this.head = newHead
this.size++
} else {
newHead.next = oldHead
oldHead.prev = newHead
this.head = newHead
this.size++
}
return this.head
}
insert(value) {
const newNode = new Node(value)
const prevNode = this.tail
if(!this.head) {
this.head = newNode
} else {
this.tail.next = newNode
newNode.prev = prevNode
}
this.tail = newNode
this.size++
return this
}
insertAtIndex(value, position) {
const node = new Node(value)
if(position < 1) this.insertNewHead(value)
if(position > this.size) {
this.tail.next = node
node.prev = this.tail
this.tail = node
this.size++
return this
}
let count = 0
let previous = this.head 
let current = previous.next
while(count !== position -1) {
previous = current
current = current.next
count++
}
node.next = current
previous.next = node
node.prev = previous
this.size++
return node
}
insertBefore(value, position) {
return this.insertAtIndex(value, position - 1)
}
insertAfter(value, position) {
return insertAtIndex(value, position + 1)
}
forEach(cb) {
let node = this.head;
while (node) {
cb(node.value);
node = node.next;
}
}
print() {
let result = [];
this.forEach(function(value) {
result.push(value);
});
return result.join(', ');
}
removeHead(){
let oldHead = this.head;
let newHead = oldHead.next;
this.head = newhead;
oldHead.next = null;
this.size--;
return oldHead;
}

}

使用print((之前7、5、1、2、3、8、6

ll.removeAtIndex(4(7、5、1、2、8、6

然而，我还是看到了这一点，我仍然看到6 prev指向3

LinkedList {
head:
Node {
value: 7,
next: Node { value: 5, next: [Node], prev: [Circular] },
prev: null },
tail:
Node {
value: 6,
next: null,
prev: Node { value: 3, next: null, prev: null } },
size: 6 }

我是否正确重置了节点指针？这是意料之中的结果吗？这个节点会被垃圾收集吗？6不是应该指8吗？

将元素添加到列表的代码：

const ll = new LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.findNode(1)
ll.insertNewHead(7)
ll.insertAtIndex(5,1)
ll.tail
ll.insertBefore(6, 10)
ll.insertAtIndex(8, 5)
ll.print()
ll.removeAtIndex(4)
console.log(ll)
ll.print() 

Answer 1

问题不在于removeAtIndex，而在于insertAtIndex，它确实分配了node.next = current，但没有分配current.prev = node。这使得节点6仍然引用节点3，而它实际上应该引用节点8。