对于一个具有n个结点的单链表,在p所指结点后插入一个新结点的时间复杂度为_______;在给定值为x的结点后插入一个新结点的时间复杂度为_______。

admin2014-12-25  12

问题 对于一个具有n个结点的单链表,在p所指结点后插入一个新结点的时间复杂度为_______;在给定值为x的结点后插入一个新结点的时间复杂度为_______。

选项

答案O(1) O(n)

解析 在指定结点后插人一个结点,无须查找插入位置,故其时间复杂度是O(1);而对给定值的结点,因为不知道它的存放位置,所以需要从表头处开始查找,故其时间复杂度是O(n)。
转载请注明原文地址:https://kaotiyun.com/show/4iVx777K
0

最新回复(0)