链表表尾插入和删除的时间复杂度

ZhangFinder 发布于 2017/03/07 18:40
阅读 682
收藏 0

今天面试的时候,面试官问我链表表尾插入和删除的时间复杂度,我答是o(n),面试官问了我几遍确不确定,难道不是o(n)吗?求大侠解惑

以下是问题补充:

@ZhangFinder:链表是单链表 (2017/03/09 09:35)
加载中
0
您的好友
您的好友

o(n)没毛病 

0
十三哥
十三哥
单链表还是双链表?不管哪个是否有指针指向尾节点
0
googlewell
googlewell
算法与数据结构,早忘光了
0
乌龟壳
乌龟壳

如果说是最简单的链表,是O(n),如果是稍微优化过的链表是O(1)

一般实用的链表都是O(1)的,它会存有First/Last节点的指针,无论是Shift(插入头)还是Add(插入尾)都是O(1)。并且实用的链表还会直接存储链表元素个数,进行count的时候直接取就行了。

存储如上所说的First/Last/count的指针的地方,并不是链表的每一个node上,还是另外有一个结构去存的。

0
AutoPlus
AutoPlus

单链表, 插入是 o(1), 删除是 o(n). 双链表, 插入删除都是 o(1).

AutoPlus
AutoPlus
回复 @ZhangFinder : 修正一下, 单链表插入应该是 o(n) --- 最快尾部 o(1), 最慢倒数第二个 o(n-1) 即 o(n).
AutoPlus
AutoPlus
回复 @ZhangFinder : 删除的话, 你定位到最后一个, 没法找到 prev, 只能从头扫描过来, 找到倒数第二个. 双向的话,因为都有 next prev, 利用 List 找到最后一个, 直接定位到 prev 就可以.
AutoPlus
AutoPlus
回复 @ZhangFinder : 作为链表, 包括链表头和链表meta(元数据)维护者. 可以定义为 ListNode (链表头) 和 List(维护者). Node 包含 next (prev 双向). List 包含第一个 Node 和 最后一个 Node, 以提供 iterate (迭代, 循环). 如果是单向, 插入的话, 通过 List 可以立刻定位到最后一个.
鱼米三香
鱼米三香
感觉问的好笼统,需要问清楚是单双链表,有没头尾指针,任意增删还是头尾增删,链表如果做了index就都是o(1)了
ZhangFinder
ZhangFinder
为什么插入和删除不一样呀?
0
ZhangFinder
ZhangFinder

面试官说的是单链表

0
雨翔河
雨翔河

双向循环链表的话直接就能到达尾节点。

0
蓝风970655147
蓝风970655147

或许这个问题中有些东西 你应该确认的更加详细一点, 对了, 你应该询问面试官的回答, 或许你们考虑的不在同一条线上

ZhangFinder
ZhangFinder
恩恩,面试的时候太紧张了
返回顶部
顶部