Complexity of ConcurrentSkipListSet to access the first and the last elements

Question

From what I understand, ConcurrentSkipListSet has an average complexity of O(log n) for insertion, search and removal of elements and a worst case of O(n). How about accessing the first and the last element? Is it any lower than log? I see that it retains a pointer to the head. Hence, I am guessing O(1) for the first element.

Answer 1

Yes, you are right about the head. => O(1)

However, when accessing the last one, you don't know which one it is, since after all it's a linked-list. Now because it is a skip-list you get O(log n) instead of processing all elements in linear time. Here you can look for a nil next pointer, but since you don't know which one to check it is still in O(log n).

There is a difference to note between real-measured time and asymptotic approximations!

Here is a possible depiction of it:

I hope this helps.