首页 > 试题广场 >

在有序双向链表中定位删除一个元素的平均时间复杂度为？

[单选题]
在有序双向链表中定位删除一个元素的平均时间复杂度为（）？ 
  • O(1)
  • O(N)
  • O(logN)
  • O(N*logN)
查看答案及解析
添加回答
推荐
牛客-007头像 牛客-007
答案：B
链表只能顺序查找
定位一个元素的时间为O(N)，删除一个元素的时间为O(1)
编辑于 2015-02-06 11:28:24 回复(3)
冰封无痕头像 冰封无痕 
题目说的是定位删除一个元素，在链表中定位一个元素的时间复杂度O(N),而插入和删除一个元素的时间复杂度为O(1)

发表于 2016-03-13 21:30:38 回复(2)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
总感觉双向可以糕点事情，结果发现链表不支持随机访问，所以管你双向还是双向循环 永远为O(n)
发表于 2018-06-11 09:44:53 回复(0)
牛客113839108号头像 牛客113839108号
链表只能顺序查找
定位一个元素的时间o(n),删除一个元素的时间为o(1),删除一个元素的时间为o(1)
发表于 2022-01-12 20:40:35 回复(0)
翻红的番茄头像 翻红的番茄
双向链表最差情况是在中间查找，时间为（n/2）所以时间复杂度也为O（n）
发表于 2020-01-08 21:26:33 回复(0)
sunlight_run头像 sunlight_run
定位为O(n)，删除为O(1)，注意题目可能挖坑
发表于 2017-06-07 20:37:16 回复(0)
MyGoodHelper头像 MyGoodHelper
A
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。链表删除或插入元素时间复杂度 O(1)
发表于 2015-01-14 12:50:38 回复(1)
Ricardo.Leo头像 Ricardo.Leo
发表于 2022-09-17 11:45:25 回复(0)
你的offer对我打了烊头像 你的offer对我打了烊
审题，写的是定位删除，定位是O（n），删除是O（1）
发表于 2020-02-23 09:43:18 回复(0)
017号头像 017号
定位一个元素是O(n)删除是O(1)
发表于 2022-10-08 09:34:18 回复(0)
恶寒轻轻头像 恶寒轻轻
查找的时间复杂度为O（n） 删除或插入的时间复杂度为O（1）
发表于 2021-11-20 13:55:51 回复(0)
做一个蜗牛头像 做一个蜗牛
不知道哪位大神能正真计算T(n)吗
发表于 2021-08-27 16:18:18 回复(0)
牛客580050057号头像 牛客580050057号
链表不支持随机访问，不管是双向还是双向循环，永远是O(n)
发表于 2021-05-12 11:28:53 回复(0)
Despacito007头像 Despacito007
<p>链表只在插入 删除时才能凸显优势</p>
发表于 2020-10-22 21:35:28 回复(0)
Weserubung头像 Weserubung
查找的平均时间为 （n+1）/2，故为o（n）
发表于 2020-03-15 15:07:03 回复(0)
PCChris头像 PCChris

在顺序表中做相同的操作的时间复杂度是多少呢？

发表于 2019-02-19 11:28:54 回复(0)
安琪拉的魔法书头像 安琪拉的魔法书

链表，定位一个元素o  n删除为o 1

发表于 2018-10-20 11:42:14 回复(0)
梦境迷离头像 梦境迷离
不是有序双循环。。
发表于 2017-11-29 19:40:00 回复(0)
我是超越迷妹了😘头像 我是超越迷妹了😘
如果已经知道插入的位置的话时间复杂度为O(1)   ——只需要改变指针就可以了

发表于 2017-09-30 18:19:03 回复(0)
bealikeflower头像 bealikeflower
定位和删除
发表于 2017-06-13 17:08:58 回复(0)
huixieqingchun头像 huixieqingchun 
链表只能顺序查找，定位一个元素只能从头查找，所以时间复杂度为O（n）

发表于 2016-04-28 19:46:34 回复(0)
提交观点

问题信息

链表 搜狐 复杂度
上传者：云间月
难度：
22条回答 21489浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号