top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

What is SkipList DataStructure? How can it be implemented in .Net?

+2 votes
102 views
What is SkipList DataStructure? How can it be implemented in .Net?
posted Apr 28, 2014 by Merry

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button

1 Answer

+1 vote
 
Best answer

The idea is simple, we create multiple layers so that we can skip some nodes. See the following example list with 16 nodes and two layers.

enter image description here

The upper layer works as an “express lane” which connects only main outer stations, and the lower layer works as a “normal lane” which connects every station.

Suppose we want to search for 50, we start from first node of “express lane” and keep moving on “express lane” till we find a node whose next is greater than 50. Once we find such a node (30 is the node in following example) on “express lane”, we move to “normal lane” using pointer from this node, and linearly search for 50 on “normal lane”. In following example, we start from 30 on “normal lane” and with linear search, we find 50. Credit: http://www.geeksforgeeks.org/skip-list/

Now coming for the .net implementation, I would suggest please look at the http://www.codeproject.com/Articles/4897/A-Skip-List-in-C

answer Apr 28, 2014 by Salil Agrawal
Similar Questions
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...