> SkipList needs less space compared to Self-balancing BST. The SkipList has less pointer overhead (Level and the next pointer) compared to a self-balancing BST where each node has two pointers (left and right)
1. So each node in both data structures have same number of pointers right? How does that make skip-list more memory efficient?
2. Aren't we also storing few elements multiple times? Shouldn't that make skip-list consume more memory?
3. For lists at higher level, how do we insert in the middle of the linked list if we don't store next and previous pointer (along with height to move down).
1&2. To quote the author from the official paper of SkipList: "SkipList can easily be configured to require an average of 1(1/3) pointers per element (or even less)." That should be primarily because you don't need level pointers at the last level and only need next pointers. There is some additional math required to calculate for nodes at the higher level which is up for discussion. However, you would need 2 pointers for every node in the Self-balancing BST.
3. For SkipList, you don't need to store the previous pointer. you can just work around by storing the level and the next pointer. While doing comparisons with the new element to be inserted, just compare the next pointer value instead of actually moving to it.
For example: if (new_element_value <= curr->next.value) = true
then, you know that you have to insert after the curr pointer.
Thank you for the interesting article!
> SkipList needs less space compared to Self-balancing BST. The SkipList has less pointer overhead (Level and the next pointer) compared to a self-balancing BST where each node has two pointers (left and right)
1. So each node in both data structures have same number of pointers right? How does that make skip-list more memory efficient?
2. Aren't we also storing few elements multiple times? Shouldn't that make skip-list consume more memory?
3. For lists at higher level, how do we insert in the middle of the linked list if we don't store next and previous pointer (along with height to move down).
Hey Vipin, great questions.
1&2. To quote the author from the official paper of SkipList: "SkipList can easily be configured to require an average of 1(1/3) pointers per element (or even less)." That should be primarily because you don't need level pointers at the last level and only need next pointers. There is some additional math required to calculate for nodes at the higher level which is up for discussion. However, you would need 2 pointers for every node in the Self-balancing BST.
Refer to the first few paragraphs of the first page here: https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf
3. For SkipList, you don't need to store the previous pointer. you can just work around by storing the level and the next pointer. While doing comparisons with the new element to be inserted, just compare the next pointer value instead of actually moving to it.
For example: if (new_element_value <= curr->next.value) = true
then, you know that you have to insert after the curr pointer.
Hope it helps..