我已经在JavaScript中实现了以下链表数据结构:
```html
动画不断地添加和移除。我在动画的
你可以看到,在迭代链表的过程中,每秒钟会多次进行操作,偶尔会删除一个节点。
如何在不影响性能的情况下实现O(1)的链表删除?
```html
我已经在JavaScript中实现了以下链表数据结构:
```class Node {
constructor(data, list) {
this.data = data;
this.list = list;
this.prev = null;
this.next = null;
}
remove() {
if (this.prev) {
this.prev.next = this.next;
} else {
this.list.start = this.next;
}
if (this.next) {
this.next.prev = this.prev;
} else {
this.list.end = this.prev;
}
this.next = null;
this.prev = null;
this.list.length -= 1;
}
}
class LinkedList {
constructor() {
this.end = null;
this.start = null;
this.length = 0;
}
append(data) {
const node = new Node(data, this);
if (!this.start) {
this.start = node;
}
if (this.end) {
node.prev = this.end;
this.end.next = node;
}
this.end = node;
this.length += 1;
return data;
}
remove() {
if (this.end) {
return this.end.remove();
}
}
*[Symbol.iterator]() {
let current = this.start;
while (current) {
yield current;
current = current.next;
}
}
}
module.exports = LinkedList;
我这样使用它来更新动画列表:
static update(timeDelta) {
for (let node of this.animations) {
const animation = node.data;
if (animation.animating) {
animation.update(timeDelta);
} else {
node.remove();
}
}
}
node.remove()
这行代码会导致我的游戏明显卡顿,我怀疑它在触发垃圾回收。讽刺的是,如果我注释掉node.remove()
这行代码并允许链表无限增长,游戏就可以平稳运行。动画不断地添加和移除。我在动画的
update
函数中添加了一些日志记录:start iterating linked list
removing
ms elapsed: 0.45499999999992724
end iterating
start iterating linked list
removing
ms elapsed: 0.455000000000382
end iterating
start iterating linked list
removing
ms elapsed: 0.13000000000010914
end iterating
start iterating linked list
(13) updating
ms elapsed: 2.200000000000273
end iterating
你可以看到,在迭代链表的过程中,每秒钟会多次进行操作,偶尔会删除一个节点。
如何在不影响性能的情况下实现O(1)的链表删除?
delete
关键字删除它们吗?@Blindman67 那是个好主意。所以这个链表抽象因为GC而变得无意义? - Maros