data-structures Linked List Skip List
Example
Skip lists are linked lists that allow you to skip to the correct node. This is a method which is way more fast than a normal singly linked list. It is basically a singly linked list but the pointers not going from one node to the next node, but skipping few nodes. Thus the name "Skip List".
Is this different from a Singly Linked List?
Yes, it is.
A Singly Linked List is a list with each node pointing to the next node. A graphical representation of a singly linked list is like:
A Skip List is a list with each node pointing to a node which might or might not be after it. A graphical representation of a skip list is:
How does it work?
The Skip List is simple. Let's say we want to access node 3 in the above image. We can't take the route of going from the head to the fourth node, as that is after the third node. So we go from the head to the second node, and then to the third one.
A graphical representation is like:
References
