hello for my course i need to build a skiplist but i do not understand it any chance can someone help me understand how it works?
im familiar with link list but dont understand the levels part
#SkipList explainatio please
floral sequoia
elfin marshBOT
<@&987246964494204979> please have a look, thanks.
floral sequoia
anyone to the rescue? lol
nova shore
hello for my course i need to build a skiplist but i do not understand it any ch...
ur kinda assuming people just know what a "skip list" is, and further what ur course specifically understands under that term
it would help if u would also post the definitions and material u have on that
in case its talking about what most people understand under this term, theres good explanations with animations available on wikipedia:
https://en.wikipedia.org/wiki/Skip_list
so it would help if u first read that and then ask a more specific question so we know what exactly is unclear to u
🙂
the first paragraph in section Description explains it really well
its multiple linked lists, whereas each higher level only contains a few of the original nodes
so it acts as an express lane to walk faster through the list
so if u want to reach the 73th index of a list that has 100 elements, u can use the express lanes to move there faster
so if ud for example insert sth between the 7th and 8th index u could walk there like this
and by that only have to walk over 4 nodes instead of 7
if the levels are organized logarithmic, u can cut down the amount of nodes u have to visit from O(n) to O(log n)
which is almost like constant time O(1)
so the performance improvement for walking around in the list is huge
a related concept is called gallop search