这两个操作的时间复杂度是否等于 O(log n)？记住：列表是有序的，总是有序的，而不是双重链接的。
问问题
1100 次
1 回答
8
有序链表中的插入和删除都是O(n)-因为您首先需要找到要删除/添加的内容[在删除中找到相关节点，并在插入中-找到它的正确位置]-即O(n)-即使list 是有序的，因为您需要在从头部迭代时到达这个地方。
一种允许快速插入、删除和查找的高效特殊类型列表称为跳过列表，它使用更多节点在非相邻节点之间快速迭代
于 2012-04-18T21:54:30.930 回答