4 - Skip List

 Skip List in C

#include<stdio.h>

# define L 3

struct node {

    int val;

    struct node* next[3];

} *head = 0, *temp, *ptr1 = 0, *ptr2 = 0, *new1, *prev;

int main() {

    int ch, x, cost, c = 0, max, min;

    char res, name[30];

    do {

        printf("1.Add\n2.Display\n3.Search\nChoose any 1: \t");

        scanf("%d", &ch);

        switch(ch) {

            case 1:

                do {

                    new1 =(struct node*)malloc(sizeof(struct node));

                    for(int i=0; i<L; i++) {

                        new1->next[i] = 0;

                    }

                    printf("Enter data for the node : \t");

                    scanf("%d", &new1->val);

                    for(int i=0; i<L; i++) {

                        new1->next[i] = 0;

                    }

                    if(head == 0) {

                        head = new1;

                        c++;

                    } else {

                        temp = head;

                        while(temp->next[0] != 0) {

                            temp = temp->next[0];

                        }

                        temp->next[0] = new1;

                        c++;

                    }

                    printf("\nDo you want to add more: \t");

                    scanf(" %c", &res);

                } while(res == 'y');

                int ct = 1;

                for(int i=1; i<L; i++) {

                    temp = head->next[i-1];

                    for(prev = head; temp != 0; temp = temp->next[i-1]) {

                        ct++;

                        if(ct % L == 0) {

                            prev->next[i] = temp;

                            prev = temp;

                        }

                    }

                    ct = 1;

                }

            break;

            case 2:

                temp = head;

                for(int i=0; i<L; i++) {

                    printf("\n\n*******\tLevel %d\t********\n\n", i+1);

                    while(temp != 0) {

                        printf("%d -> ", temp->val);

                        temp = temp->next[i];

                    }

                    printf("NULL");

                    temp = head;

                }

            break;

            case 3:

                do {    

                    printf("\nEnter the value to be searched : \t");

                    scanf("%d", &x);

                    prev = head;

                    if(head == 0 || x < head->val) {

                        printf("\n\nData can't be found");

                    } else {

                        int i = L-1, ct = 0, found = 0;

                        temp = head;

                        while(i >= 0 && found == 0) {

                            if(temp->val == x) {

                                found = 1;

                                ct++;

                                printf("\n%d compared with %d", x, temp->val);

                                break;

                            }

                            else if(temp->val < x) {

                                ct++;

                                printf("\n%d compared with %d", x, temp->val);

                                prev = temp;

                                temp = temp->next[i];

                            }

                            else if(temp == 0) {

                                i--;

                                temp = prev->next[i];

                            } else {

                                printf("\n%d compared with %d", x, temp->val);

                                ct++;

                                i--;

                                temp = prev->next[i];

                            }

                        }

                        if(found == 0) {

                            printf("\n\n******** Key not found *********\n");

                        } else {

                            printf("\n\n********************************************************************************\n\nNo of comparisons are: %d\n\n********************************************************************************\n", ct);

                        }

                    }

                    printf("\nDo you want to search more: \t");

                    scanf(" %c", &res);

                } while(res == 'y');

            break;

        }

        printf("\n\n****************************************************\n****************************************************\n\nDo you want to continue: \t");

        scanf(" %c", &res);

    } while(res == 'y');

}