JavaScript linked list causing garbage collection

Question

I implemented the following linked list data structure in 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;

I use it to update the list of animations:

static update(timeDelta) {
  for (let node of this.animations) {
    const animation = node.data;

    if (animation.animating) {
      animation.update(timeDelta);
    } else {
      node.remove();
    }
  }
}

The line node.remove()causes a very noticeable lag in my game. I suspect this is causing garbage collection. Sorry if I comment on the line node.remove()and let the linked list grow forever, the game will run smoothly.

Animations are constantly added and deleted. I added a few entries to the animation function 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

You can see that the linked list is repeated many times per second when a random node is deleted.

How can I remove O (1) from a list without actually degrading performance?

Answer 1

node.remove() . , .

. - , update .

- " ". , :

while (current) {
  yield current;
  // after yielding, in the `update` function, we have
  //    node = current
  // and most importantly
  //    node.remove()
  // which assigns (with `this` being `node`)
  //    this.next = null;
  // then the iteration is resumed
  current = current.next;
}

. node:

let next = this.start;
while (next) {
  const current = next;
  next = current.next;
  yield current;
}

( - ), , , , node .

this.next = null;
this.prev = null;

remove node, . GC.

---

- , / . , ( ?) Array, :

function filter(array, callback) {
    var i=0, j=0;
    while (j < array.length) {
        if (callback(array[j]))
            array[i++] = array[j++];
        else
            array[i] = array[j++];
    }
    array.length = i;
}
function update(timeDelta) {
    filter(animations, animation => {
        var keep = animation.animating;
        if (keep) animation.update(timeDelta);
        return keep;
    });
}

( filter, , i===j)