如果 deletion/insertion 数组的最终时间复杂度相等，为什么要使用链表？
Why use linked lists, if at the end time complexity from arrays for deletion/insertion is equal?
我有以下问题。为什么要使用链表，如果删除数组元素的时间复杂度是 O(n) 而链表（给定索引）也是 O(n) 因为我还需要搜索整个列表？
虽然渐近复杂度可能相同，但常数因子可能非常不同。特别是，您可能拥有一组“大”东西，移动或复制这些东西的成本很高，但匹配起来却很便宜。因此，对于链表，您执行（快速）O(n) 搜索以查找元素，然后执行 O(1) 到 insert/remove。对于数组，您需要进行相同的 O(n) 搜索，然后将数组中的所有其他元素缓慢移动到 make/remove space.
您也可能有另一个连接的数据结构（例如散列 table），具有快速查找能力，可以为您的集合提供参考。在这种情况下，您可以在 O(1) 时间内在列表中找到一个元素，然后在 O(1) 时间内将其删除。
另一个优点是列表更适合原子更新——single-link 列表可以通过单个（原子）指针写入来更新（插入或删除）。
我有以下问题。为什么要使用链表，如果删除数组元素的时间复杂度是 O(n) 而链表（给定索引）也是 O(n) 因为我还需要搜索整个列表？
虽然渐近复杂度可能相同，但常数因子可能非常不同。特别是，您可能拥有一组“大”东西，移动或复制这些东西的成本很高，但匹配起来却很便宜。因此，对于链表，您执行（快速）O(n) 搜索以查找元素，然后执行 O(1) 到 insert/remove。对于数组，您需要进行相同的 O(n) 搜索，然后将数组中的所有其他元素缓慢移动到 make/remove space.
您也可能有另一个连接的数据结构（例如散列 table），具有快速查找能力，可以为您的集合提供参考。在这种情况下，您可以在 O(1) 时间内在列表中找到一个元素，然后在 O(1) 时间内将其删除。
另一个优点是列表更适合原子更新——single-link 列表可以通过单个（原子）指针写入来更新（插入或删除）。