CODEWITHSUNDEEP
data-structuresskip-lists
ms.twenty four
ms.twenty four

Reputation: 31

skiplist- i really need an explanation ,how does it insert and delete

i really dont understand the probabilty thing of this list. in addition to the statement"we have to examine no more than n/2 + 1 nodes (where n is the length of the list).Also giving every fourth node a pointer four ahead (Figure1c) requires that no more than n/4 + 2 nodes be examined". this statement i read in the following link:ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

Upvotes: 2

Views: 3585

Answers (4)

Jim Mischel
Jim Mischel

Reputation: 134045

What you're not understanding is that every node has a link at level 1. That is, at the lowest level, the data structure is essentially a linked list. Searching for a node using this is of course an O(n) operation.

Each node of the skip list has at least one link: the one at level 1. On average, half of the nodes also have a link at level 2. If this was the highest level at which a link existed, then you could find an arbitrary node in O(n/2). Basically, you follow the 2nd level nodes until either you find the item you're looking for, or until you get to a node whose value is larger than the one you're looking for. At that point, you step down to the level 1 nodes and search forward from the previous node (i.e. the one that's less than the one you're looking for).

Again on average, 1/4 of the nodes have a link at level 3. Using these, you can find an arbitrary node in O(n/4). You first search the level 3 nodes until you either find the node or go past it, then drop down to the level 2 nodes from that point, and to the level 1 nodes if don't find the node at level 2.

If you follow the math, you can see that if your maximum level is m, then as long as you have less than 2^m nodes in the skip list, your amortized average search time will be O(log2(n)), where n is the number of items in the list.

So the structure of a skip list node is like this:

SkiplistNode
{
    int level;
    SomeType data; // the data held in the node
    SkiplistNode* forwards[]; // an array of 'level' forward references
}

If a node has a level value of 1, then there will be just one item in the forwards array. If it's at level 4, then there will be four entries: one for each of levels 4, 3, 2, and 1.

As it turns out, the average size of the forwards array is 2. That follows the progression 1 + 1/2 + 1/4 + 1/8 + 1/16, + 1/32, ... That is:

Every node has a link at level 1
1/2 of the nodes have a link at level 2
1/4 of the nodes have a link at level 3
1/8 of the nodes have a link at level 4
etc.

Is that more clear now?

Upvotes: 3

Praveen Kumar
Praveen Kumar

Reputation: 1624

A somewhat easier to understand explanation can be found here : http://igoro.com/archive/skip-lists-are-fascinating/

Upvotes: 1

Pawel Zubrycki
Pawel Zubrycki

Reputation: 2713

Lecture from MIT about skip lists: http://video.google.com/videoplay?docid=-6710586843601387849#

Upvotes: 1

Billy ONeal
Billy ONeal

Reputation: 106589

Skip lists are explained quite well in their Wikipedia article. If you have a specific question about the data structure itself feel free to ask them though.

Upvotes: 2

Related Questions