java - ConcurrentSkipListSet 访问第一个和最后一个元素的复杂性

Question

据我了解，ConcurrentSkipListSet插入、搜索和删除元素的平均复杂度为 O(log n)，最坏的情况为 O(n)。如何访问第一个和最后一个元素？它是否低于对数？我看到它保留了一个指向头部的指针。因此，我猜测第一个元素是 O(1)。

Answer 1

是的，关于头部，你是对的。=>O(1)

但是，当访问最后一个时，您不知道它是哪一个，因为它毕竟是一个链表。现在因为它是一个跳过列表，O(log n)而不是在线性时间内处理所有元素。在这里您可以查找 nil next 指针，但由于您不知道要检查哪个指针，它仍在O(log n).

实际测量的时间和渐近近似之间存在差异！

这是一个可能的描述：

我希望这有帮助。