Skip List | Set 1 (Introduction)

Can we search in a sorted linked list in better than O(n) time?
The worst case search time for a sorted linked list is O(n) as we can only linearly traverse the list and cannot skip nodes while searching. For a Balanced Binary Search Tree, we skip almost half of the nodes after one comparison with root. For a sorted array, we have random access and we can apply Binary Search on arrays.

Can we augment sorted linked lists to make the search faster? The answer is Skip List. 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. 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.

What is the time complexity with two layers? The worst case time complexity is number of nodes on “express lane” plus number of nodes in a segment (A segment is number of “normal lane” nodes between two “express lane” nodes) of “normal lane”. So if we have n nodes on “normal lane”,  nodes on “express lane” and we equally divide the “normal lane”, then there will be  nodes in every segment of “normal lane” .  is actually optimal division with two layers. With this arrangement, the number of nodes traversed for a search will be . Therefore, with  extra space, we are able to reduce the time complexity to .

problem defination is available at : skip-list

code :


#include<stdio.h>
#include<stdlib.h>
#include<math.h>


struct node
{
int data;
  struct node * link;
};

struct skipNode
{
int data;
struct node *ll;
struct skipNode *link;

};

struct node *createNode(int data)
{
struct node *p=NULL;
p=(struct node *)malloc(sizeof(struct node));
p->data=data;
p->link=NULL;

return p;

}


struct skipNode *createSkipNode(struct node *ll)
{
struct skipNode *p=NULL;
p=(struct skipNode *)malloc(sizeof(struct skipNode));
p->data=ll->data;
p->ll=ll;
p->link=NULL;

return p;

}


struct node *traverseTillEnd(struct node *head) //will return the pointer to the last node.
{
struct node *p=head;

if(head==NULL)
{
return NULL;
}
else
{
while((p->link)!=NULL)
{
p=p->link;
}

return p;
}


}

struct skipNode *traverseSkipTillEnd(struct skipNode *head)
{
struct skipNode *p=NULL;
p=head;

if(head==NULL)
{
return NULL;
}
else
{
while((p->link)!=NULL)
{
p=p->link;
}

return p;


}


}



struct node *insert(struct node * head,int data)
{
struct node *p=NULL;

if(head==NULL)
{
head=createNode(data);
return head;
}
else
{
// traverse the node till end.
p=traverseTillEnd(head);
p->link=createNode(data);

return head;
}


}


struct skipNode *skipInsert(struct skipNode *head,struct node *ll) // pass the head of skip node , link to the linked list node.
{
struct skipNode *p=NULL;

printf("insid insert...\n");

if(head==NULL)
{
head=createSkipNode(ll);
printf("\n data is %d",head->data);
return head;
}
else
{
printf("insid else...\n");
// traverse the skipList to the end...
p=traverseSkipTillEnd(head);
printf("\n data is %d\n",p->data);
p->link=createSkipNode(ll);

return head;
}

}

int count(struct node *head) // return the number of nodes the list have.
{
int i=0;
if(head==NULL)
{
return 0;
}
else
{
while(head!=NULL)
{
i++;
head=head->link;
}

return i;
}

}

void printList(struct node *head)
{
while(head!=NULL)
{
printf("-%d-",(head->data));
head=head->link;
}

printf("\n");

}


void printSkipList(struct skipNode *head)
{
while(head!=NULL)
{
printf("-%d-",(head->data));
head=head->link;
}

printf("\n");

}



struct skipNode *createSkipList(struct node *head) // create new linked list , called skip list and return the pointer to the head node of the skip list.
{
int skipNodeCount;
int nodeCount=count(head);
int segmentCount=0;
int temp;
struct skipNode *skipHead=NULL;
struct node *ptrToLL=NULL;


if(head==NULL)
{
return NULL;
}
else
{

skipNodeCount=(int)sqrt((double)count(head));

printf("\n\n %d\n",skipNodeCount);

// decide how many number of nodes shoud be between two skip list nodes , lets call it Segment.

segmentCount=nodeCount/skipNodeCount;

printf("\n\n %d\n",segmentCount);

// create the skip list.

ptrToLL=head;





while(skipNodeCount!=0)
{

skipHead=skipInsert(skipHead,ptrToLL);

if(skipNodeCount==1)
{
break;
}

ptrToLL=ptrToLL->link;
temp=segmentCount;

while(temp!=0)
{

ptrToLL=ptrToLL->link;
temp--;

}


skipNodeCount--;

}


}


return skipHead;


}


int main(int argc,char *argv[])
{
int i=0;
int val[argc];
struct node *head=NULL;
struct skipNode *skipHead=NULL;

printf("%d number of argument provided.\n",(argc-1));

for(i=1;i<argc;i++)
{
val[i]=atoi(argv[i]); // convert Ascci to Int

head=insert(head,val[i]);

}

printList(head);

skipHead=createSkipList(head);

printf("\n\n");

printSkipList(skipHead);

return 0;


}


// now  create the function to find the element in the linked list from the searching in the skip list by your own,

// compile :  gcc -c skipList.c
// link :  gcc -o skipList skipList.o -lm
// execute :  ./skipList 10 15 20 25 26 28 29 25 40 45