Сложность ConcurrentSkipListSet для доступа к первым и последним элементам

Question

Из того, что я понимаю, ConcurrentSkipListSet имеет среднюю сложность O(log n) для вставки, поиска и удаления элементов и наихудший вариант O(n). Как насчет доступа к первому и последнему элементу? Это ниже, чем журнал? Я вижу, что он сохраняет указатель на голову. Следовательно, я предполагаю O(1) для первого элемента.

Answer 1

Да, вы правы насчет головы. => O(1)

Однако, при доступе к последнему, вы не знаете, какой это, так как в конце концов это связанный список. Теперь, потому что это список пропуска вы получаете O(log n) вместо обработки всех элементов за линейное время. Здесь вы можете найти нулевой следующий указатель, но поскольку вы не знаете, какой из них проверить, он все еще находится в O(log n),

Существует разница между реальным измерением времени и асимптотическими приближениями!

Вот возможное описание этого:

Надеюсь, это поможет.