• 题目
• 答案

题目

在有序双向链表中定位删除一个元素的平均时间复杂度为（）？
（1）O(1)
（2）O(N)
（3）O(logN)
（4）O(N*logN)

答案

（2）O(N)

链表只能顺序查找
定位一个元素的时间为O(N)，删除一个元素的时间为O(1)。
所以总的定位删除一个元素的平均时间复杂度是 O(N)。