You are here
单链表删除和插入的时间复杂度是O（1）还是O（n）啊
星期三, 2018-04-25 16:58 — adminshiping1
| 有两种说法： 1、说单链表删除和插入时需要移动指针找到需要删除或插入的位置，因此时间复杂度为O（n） 2、说单链表删除和插入时不需要移动结点，故时间复杂度为O（1） 不清楚哪种说法是正确的了，请各位高手指点，谢谢啊 |
| 既然 顺序表插入删除的时间复杂度为0（n），链表插入删除的时间复杂度也为O(n) 那链表比顺序表的优越之处又是什么呢？ |
显然是o（n） 你每次插入的时候或者删除 不都要对链表进行查找吗 这不就和表中的元素个数有关了
单链表对已经给定的位置（比如删除p指针指向的下一个结点）的插入删除操作是O(1)，而顺序表无论如何都是O(n)。
时间复杂度就是 O(n)。
| o(n),时间是这个， |
| 关键是理解题意，说的是不是已经给定位置，若已经给定位置，则执行插入操作为0(1) 需查找位置时为0（N） |
| 分查找和 对指针的操作 前者O(n) 对指针的操作O(1) |
| 具体问题具体分析!!!!! |
删除或插入之前你得先找到该结点,而查找的时间复杂度就是O(n).
| 同意8＃的帖子，要看插入删除的位置，还要看是否有头尾指针。。。 |
| 链表在删除的时候不用将之后的元素移动啊 顺序表要移动的 代价相当大 |
普通分类: