尽管对于两种数据结构都需要 O(n)，但链表如何比插入和删除操作的数组更快? [英] How is a linked list faster than an array for insert and delete operations although it takes O(n) for both data structures?

问题描述

在数组中插入和删除操作的最坏情况运行时间是 O(n)，因为我们可能需要进行 n 次移位.

The worst case running time of Insert and delete operations in an array is O(n), because we might need to make n shifts.

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

Same is the case for linked list too, if we want to insert or delete ith element we might need to traverse the whole list to reach the position where insert/delete is expected to be done. So Linked list also takes O(n) time.

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

So why is linked list preferred where insert/delete intensive operations are done.

推荐答案

如果要插入/删除数组中的第 i 个元素，由于索引的原因，搜索只需要 O(1).例如，您可以通过 array[i] 访问数组的第 i 个元素.但是，在最坏的情况下，插入/删除该元素将花费 O(n) 时间.例如，如果在位置 0 插入一个元素，则必须将所有元素向右移动一个位置，这需要遍历整个数组.

If you want to insert/delete the ith element in an array, searching only takes O(1) because of indexing. For example u can access the ith element of an array through array[i]. However, inserting/deleting that element, in the worst case, will take O(n) time. For example, if you inserted an element at position 0, you have to shift all the elements one spot to the right, which requires a traversal of the whole array.

如果你想插入/删除链表中的第 i 个元素，在最坏的情况下搜索将花费 O(n)，因为你必须在一次遍历列表一个元素时保留一个计数和一个指针.一旦到达第 i 个节点，插入/删除只需要 O(1) 时间，因为它只是指针的重新排列，没有移位.

If you want to insert/delete the ith element in an linked list, searching will take O(n) in the worst case because you have to keep a count and a pointer while traversing the list one element at a time. Once you arrive at the ith node, inserting/deleting only takes O(1) time since it's just a rearrangement of pointers, no shifting.

至于为什么在有很多插入/删除时优先使用链表，我想说的一个原因是使用链表您不需要提前知道它有多大.而对于数组，它可能必须经常调整大小以预期更多/更少的元素.

As to why linked lists are preferred when there are many inserts/deletions, I would say that one reason is that with linked lists you don't need to know how big it has to be ahead of time. Whereas with arrays, it may have to be resized often in anticipation of more/less elements.

这篇关于尽管对于两种数据结构都需要 O(n)，但链表如何比插入和删除操作的数组更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！