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

答案:2 悬赏:50 手机版

解决时间 2021-11-13 02:44

提问者网友：藍了天白赴美
2021-11-12 05:09

最佳答案

五星知识达人网友：神的生死簿
2021-11-12 06:43

线性顺序表插入某个位置时，要将其后的所有元素向后移动一位，删除时要将其后所有元素向前移
线性链表插入和删除时只需要改变其前后元素的指针追问但是他们的时间复杂度一样的啊追答时间复杂度O(n)是一个表示执行时间与问题规模关系的相对概念
n+1次操作是O(n)
2n次操作也是O(n)
那一个快一点呢？追问嗯，懂了，谢谢一直纠结在时间复杂度上了

全部回答

1楼网友：时间的尘埃
2021-11-12 07:34

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

我要举报

如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！