I had a problem in my exam dealing with 1-2-3 skip lists.

I have a problem with the insertion process in a 1-2-3 skip list. What I understand is that if the minimum of heights of 2 nodes in a 123 skip list is greater than 0, say h, then there must be at least one node, and at most 3 with height h-1 between those two. How exactly will insertion take place? Bcoz as per what I think, the skip list is empty initially. You keep adding nodes to it, all of those will be added to level 0. In no case, I'll need to promote my nodes to a higher level (as per my prof, when we add a 4th node between "those" 2 nodes- having height h and so on, either the 2nd or 3rd one is promoted to higher level, that's why i used that word, i don't know and I don't understand why do we need to do that).

I said that they will all be in zero level because for no two nodes in the skip list, the height is more than 0. So, minimum of the heights end up being zero- at no stage is the structural invariant violated. Then why, and how, do promotions come into play? What I may end up with might just be a simple linked list!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.