Java does have primitive types like int , char etc which I believe are stack allocated. Java programmers do like to "box" these into classes like "Integer" etc though.
What I find confusing about the answer is that it implies that there is some reason that a skip list (compared to another structure) would be particularly inefficient in the JVM (compared to say native C++).
Basically a skip list will cost you some extra memory by storing more pointers which allow you to "skip" ahead the list but as you add extra layers each layer will have less pointers than the one below it.
A skip list might be a bad idea if you are working a severely memory constrained system and saving memory is more important than lookup speed on your data structure. They would also of course be a bad idea if there is another structure better suited to what you are doing (B tree or whatever).
But saying "Skip lists are bad because there are too many pointers for Java" just seems like a big wtf to me, unless there is something I am missing here.
While he worded it poorly, he is correct. Kinda. In a skip list with millions of items, you're going to have something like n log(n) SkipListObjects. The references are virtually free. The objects are not.
On a typical JVM implementation, each object takes ~100 bytes. IIRC even an empty ArrayList will cost you something like 60-80 bytes.
If the extra log(n) of space complexity is going to make a difference, then a skip list might not make sense.
But honestly, if you've got millions of objects, you might want to consider a different language/environment. Java is pretty fast these days, but it will still chew up considerably more memory than most native solutions.
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.
The 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.
What I find confusing about the answer is that it implies that there is some reason that a skip list (compared to another structure) would be particularly inefficient in the JVM (compared to say native C++).
Basically a skip list will cost you some extra memory by storing more pointers which allow you to "skip" ahead the list but as you add extra layers each layer will have less pointers than the one below it.
A skip list might be a bad idea if you are working a severely memory constrained system and saving memory is more important than lookup speed on your data structure. They would also of course be a bad idea if there is another structure better suited to what you are doing (B tree or whatever).
But saying "Skip lists are bad because there are too many pointers for Java" just seems like a big wtf to me, unless there is something I am missing here.