# Skip lists

• 01-16-2003
Cela
Skip lists
Okay, I looked all over the place for ideas on how to make a skip list and everything just went overboard with nasty code I couldn't understand or just explanations of what a skip list is, which I know already. So I cheated a little. :p I started with a regular list and added the skip links in a separate function. Here's what I have, can someone tell me if I'm on the right track as well as how to destroy the entire list? I can't seem to get that to work right. I also didn't do any error checking and such, so I already know about those potential oopsies. :)
Code:

```#include <stdio.h> #include <stdlib.h> #define MAX_LEV 3 typedef struct node {   int data;   struct node *next[MAX_LEV]; } *NODE; NODE new_node(int data) {   int i;   NODE np;   np = malloc(sizeof *np);   np->data = data;   for (i = 0; i < MAX_LEV; i++)   {     np->next[i] = 0;   }   return np; } NODE set_skip(NODE list) {   int i, j, k;   NODE np, nn;   for (j = 1, k = 2; j < MAX_LEV; j++, k += 3)   {     for (i = 0, nn = np = list; np != 0; np = np->next[0], i++)     {       if (i % k == 0)       {         nn->next[j] = np;         nn = np;       }     }   }   return list; } void del_skip(NODE list) {   int i;   NODE np, nn;   for (i = MAX_LEV - 1; i >= 0; i--)   {     for (np = list->next[i]; np != 0; np = nn)     {       nn = np->next[i];       free(np);     }   } } void print_skip(NODE list) {   int i;   NODE np;   static char *lev[] = {     "->",     "----->",     "----------------->",   };   for (i = MAX_LEV - 1; i >= 0; i--)   {     for (np = list; np != 0; np = np->next[i])     {       printf("%02d%s", np->data, np->next[i] == 0 ? "\n" : lev[i]);     }   } } int main(void) {   int i;   NODE head = 0, np;   for (i = 11; i > 0; i--)   {     np = new_node(i);     np->next[0] = head;     head = np;   }   head = set_skip(head);   print_skip(head);   return 0; }```
This is the list destroyer I have so far, it bombs out with a bad pointer access on the second iteration of the outer loop
Code:

```void del_skip(NODE list) {   int i;   NODE np, nn;   for (i = MAX_LEV - 1; i >= 0; i--)   {     for (np = list->next[i]; np != 0; np = nn)     {       nn = np->next[i];       free(np);     }   }   free(list); }```
• 01-16-2003
Nick
I've never coded one of these :)
http://www.cs.umd.edu/~pugh/

From the picture it would look like you would delete
one of these things like this

Code:

```void del_skip(NODE list) {   int i;   NODE np, nn;   for (np = list->next[0]; np != 0; np = nn)   {       nn = np->next[0];       free(np);     }   }   free(list); }```
From the picture it looks like you would have 3 seperate
list but they share nodes. So it should be only necessary
to delete the level 0 nodes.
• 01-18-2003
Cela
That's for that link, it was just what I needed. Here's what I came up with
Code:

```#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_LEV 4 #define LEAK_CHECK 1 #ifdef LEAK_CHECK   int cnt;   #define LeakMalloc(x) (cnt++, malloc(x))   #define LeakFree(x) (cnt--, free(x))   #define LeakPrint() (printf("Leaks found: %d\n", cnt)) #else   #define LeakMalloc(x) (malloc(x))   #define LeakFree(x) (free(x))   #define LeakPrint() #endif typedef struct node_s {   int key;   struct node_s **forward; } *NODE; typedef struct list_s {   int level;   struct node_s *header; } *LIST; static NODE NIL; /* End of list marker */ static NODE make_node(int lvl, int key) {   NODE np = LeakMalloc(sizeof *np);   if (np == 0)   {     fprintf(stderr, "%d: Bad allocation in make_node()", __LINE__);     exit(1);   }   np->forward = LeakMalloc(sizeof *np->forward * lvl);   if (np->forward == 0)   {     fprintf(stderr, "%d: Bad allocation in make_node()", __LINE__);     exit(1);   }   np->key = key;   return np; } static int randomLevel(void) {   int lvl = 0;   while (rand() < RAND_MAX/2 && lvl < MAX_LEV)   {     lvl++;   }   return lvl; } void skip_init(void) {   NIL = make_node(0, INT_MAX); } void skip_end(void) {   LeakFree(NIL->forward);   LeakFree(NIL); } LIST skip_new_list(void) {   int i;   LIST list;   list = LeakMalloc(sizeof *list);   if (list == 0)   {     fprintf(stderr, "%d: Bad allocation in skip_new_list()", __LINE__);     exit(1);   }   list->level = 0;   list->header = make_node(MAX_LEV, -1);   for (i = 0; i < MAX_LEV; i++)   {     list->header->forward[i] = NIL;   }   return list; } void skip_free_list(LIST list) {   NODE np, nn;     for (np = list->header; np != NIL; np = nn)   {     nn = np->forward[0];     LeakFree(np->forward);     LeakFree(np);   }     LeakFree(list); } void skip_insert(LIST list, int searchkey) {   int i, lvl;   NODE update[MAX_LEV + 1];   NODE x = list->header;     /* Find the insertion point */   for (i = list->level; i >= 0; i--)   {     while (x->forward[i] != NIL && x->forward[i]->key < searchkey)     {       x = x->forward[i];     }     update[i] = x;   }   x = x->forward[0];   /* If it's a duplicate, replace */   if (x->key == searchkey)   {     x->key = searchkey;   }   /* Not found */   else   {     lvl = randomLevel();         /* Update the current max level if i is bigger */     if (lvl > list->level)     {       for (i = list->level + 1; i <= lvl; i++)       {         update[i] = list->header;       }       list->level = lvl;     }         x = make_node(lvl, searchkey);         /* Link it */     for (i = 0; i <= lvl; i++)     {       x->forward[i] = update[i]->forward[i];       update[i]->forward[i] = x;     }   } } int main(void) {   int i;   LIST list;   NODE np;   skip_init();   list = skip_new_list();   for (i = 0; i < 10; i++)   {     skip_insert(list, i);   }   for (i = 0; i < MAX_LEV; i++)   {     for (np = list->header; np != NIL; np = np->forward[i])     {       printf("%d%s", np->key, np->forward[i] == NIL ? "\n" : "->");     }   }   skip_free_list(list);   skip_end();   LeakPrint();   return 0; }```