开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >对于insert和delete操作，链表如何比数组更快，尽管这两种数据结构都需要O(n)？

问对于insert和delete操作，链表如何比数组更快，尽管这两种数据结构都需要O(n)？
EN

Stack Overflow用户

提问于 2018-07-18 01:22:25

回答 0查看 2K关注 0票数 6

数组中Insert和delete操作的最坏运行时间是O(n)，因为我们可能需要进行n次移位。

链表也是如此，如果我们想要插入或删除第i个元素，我们可能需要遍历整个列表，以到达期望完成插入/删除的位置。所以链表也需要O(n)时间。

那么为什么在执行插入/删除密集型操作时，链表是首选的。

data-structures

EN

回答

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/51387101

复制

相似问题