线性顺序表和线性链表的插入和删除时间复杂度都是O(n),那为什么说线性链表更适合插入和删除

2025-04-13 00:01:17
推荐回答(2个)
回答(1):

链表的插入和删除之所以是O(N),是因为要用O(N)顺序查找到插入点的位置,插入时间为O(N)
顺序表找到插入点的时间为O(1),但要把后面的元素全部后移一位,复杂度为O(N)。
查找所需时间比移动短多了,所以虽然复杂度都是O(N),但是链表更适合插入删除

回答(2):

线性顺序表插入某个位置时,要将其后的所有元素向后移动一位,删除时要将其后所有元素向前移
线性链表插入和删除时只需要改变其前后元素的指针