A-A+

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

2022-08-12 15:49:32 问答库阅读 196 次

问题详情

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

请帮忙给出正确答案和分析，谢谢！

正确答案：O(1) O(n)
在指定结点后插入一个结点，无须查找插入位置，故其时间复杂度是O(1)；而对给定值的结点，因为不知道它的存放位置，所以需要从表头处开始查找，故其时间复杂度是O(n)。