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

Question

如题所述

Answer 1

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

Answer 2

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

但是他们的时间复杂度一样的啊

追答

时间复杂度O(n)是一个表示执行时间与问题规模关系的相对概念
n+1次操作是O(n)
2n次操作也是O(n)
那一个快一点呢？

追问

嗯，懂了，谢谢

一直纠结在时间复杂度上了

本回答被提问者采纳