如果最终删除/插入数组的复杂性相等,为什么还要使用链表呢?

人气:188 发布:2022-10-16 标签: data-structures linked-list

问题描述

我有以下问题。为什么使用链表,如果删除数组元素的时间复杂度是O(N),对于链表(给定索引)也是O(N),因为我还需要搜索整个列表?

推荐答案

虽然渐近复杂性可能相同,但常量因子可能非常不同。尤其是,您可能有一大堆东西,它们的移动或复制成本很高,但匹配成本却很低。因此,对于链表,您执行(快速)O(N)搜索以找到一个元素,然后执行O(1)以在那里插入/删除。对于数组,您需要进行相同的O(N)搜索,然后对数组中的所有其他元素进行缓慢的O(N)移动以创建/删除空间。

您也可能有另一个连接的数据结构(如哈希表),它具有快速查找功能,提供对集合的引用。在这种情况下,您可以在O(1)时间内找到列表中的元素,然后在O(1)时间内将其删除。

另一个优点是列表更易于原子更新--单链接列表可以通过单个(原子)指针写入进行更新(插入或删除)。

514