arrays - 惰性删除对二叉树或链表有何好处/不利之处？

Question

最近，对于一个数据结构类，有人问我一个问题:延迟删除(即先标记需要删除的项目，然后在某个时候删除所有标记的项目的删除)将是有好处的/对数组，链表或二叉树不利。这是我想出的:

这将对数组有所帮助，因为您可以节省每次删除索引时转移数组所花费的时间，尽管在需要遍历数组的算法中，效率可能较低。

这对链接列表没有帮助，因为您需要遍历O(n)来标记一个无论如何都将被删除的项目。

我不确定二进制树，但是如果它是一个链表的实现，我会想像它是链表吗？

Answer 1

我认为这完全取决于环境和要求。在一般意义上，使用此方法可以标记它们，然后在以后将其删除，它们都有很多相似的优缺点。

类似的优点:
-当标记为删除时，数据结构不会移动，这使删除速度更快。
-您可以在已删除项目的顶部插入内容，这意味着插入内容也不会移位，而且插入操作可以更快完成，因为它可以覆盖第一个删除内容而不是查找列表的结尾

类似的缺点:
-浪费的空间用于已删除的项目，因为它们正坐在那里
-必须横穿两次以删除一个项目，一次标记它，再一次删除它
-许多标记为要删除的项目将污染数据结构，导致搜索需要更长的时间，因为必须搜索删除的项目。