3 ms·
The factor isn't log(n), it is a constant. Depending on the implementation, that constant is generally 2. (That's because each level is half the size of the p
by btilly 14y ago
The factor isn't log(n), it is a constant. Depending on the implementation, that constant is generally 2. (That's because each level is half the size of the previous. So n + n/2 + n/4 + ... = 2n.)
That said, I could well believe that the constant associated with a SkipList is worse than the constants with other data structures. What works well in C++ does not always translate directly to other languages.
- DanWaterworth 14y agoThe alternative would be some sort of tree. The obvious choice, some sort of balanced binary search tree, also has two pointers per item, though half of them don't point to anything.