如果最终删除/插入数组的复杂性相等,为什么还要使用链表呢? [英] Why use linked lists, if at the end time complexity from arrays for deletion/insertion is equal?
本文介绍了如果最终删除/插入数组的复杂性相等,为什么还要使用链表呢?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
推荐答案
虽然渐近复杂性可能相同,但常量因子可能非常不同。尤其是,您可能有一大堆东西,它们的移动或复制成本很高,但匹配成本却很低。因此,对于链表,您执行(快速)O(N)搜索以找到一个元素,然后执行O(1)以在那里插入/删除。对于数组,您需要进行相同的O(N)搜索,然后对数组中的所有其他元素进行缓慢的O(N)移动以创建/删除空间。
您也可能有另一个连接的数据结构(如哈希表),它具有快速查找功能,提供对集合的引用。在这种情况下,您可以在O(1)时间内找到列表中的元素,然后在O(1)时间内将其删除。
另一个优点是列表更易于原子更新--单链接列表可以通过单个(原子)指针写入进行更新(插入或删除)。
这篇关于如果最终删除/插入数组的复杂性相等,为什么还要使用链表呢?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文