data-structures - 为什么与数组相比，链表中的插入和删除更快？

Question

考虑到对于链表和数组，从中间插入/删除数据具有 O(n) 复杂度，为什么首选链表？数组的 O(n) （执行操作）是否比链表的（索引）成本更高？

标签： data-structureslinked-listbig-o

Answer 1

对于大小为“M”的数组：如果我想删除第 N 个位置的元素，那么我可以直接使用索引一次转到第 N 个位置（我不必遍历到第 N 个索引）然后我可以删除元素，直到此时复杂度为 O(1)，然后我将不得不移动其余元素（MN 移动），因此我的复杂度将是线性的，即 O(M-N+1)。因此，最后的删除或插入将给我最好的性能（如 N ~ M），而开始时的删除或插入将是最差的（如 N ~ 1）。

现在是大小为“M”的 LinkedList：如果您已经引用了要在时间复杂度为 O(1) 之后插入或删除的节点。如果不提供，我们不能直接到达LinkedList中的第N个元素，要访问第N个元素我们必须遍历N个元素，所以在LinkedList中的搜索比ArrayList更昂贵。