C++ Program to Implement Skip List

This C++ Program demonstrates the implementation of Skip List.

Here is source code of the C++ Program to demonstrate skip list. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Skip List 
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #include <cmath>
  7. #include <cstring>
  8. #define MAX_LEVEL 6
  9. const float P = 0.5;
  10. using namespace std;
  11. /*
  12.  * Skip Node Declaration
  13.  */
  14. struct snode
  15. {
  16.     int value;
  17.     snode **forw;
  18.     snode(int level, int &value)
  19.     {
  20.         forw = new snode * [level + 1];
  21.         memset(forw, 0, sizeof(snode*) * (level + 1));
  22.         this->value = value; 
  23.     }
  24.     ~snode()
  25.     {
  26.         delete [] forw;        
  27.     } 
  28. };
  29. /*
  30.  * Skip List Declaration
  31.  */
  32. struct skiplist
  33. {
  34.     snode *header;
  35.     int value;
  36.     int level;
  37.     skiplist() 
  38.     {
  39.         header = new snode(MAX_LEVEL, value);
  40.         level = 0;
  41.     }
  42.     ~skiplist() 
  43.     {
  44.         delete header;
  45.     }
  46.     void display();
  47.     bool contains(int &);
  48.     void insert_element(int &);
  49.     void delete_element(int &);        
  50. };
  51. /*
  52.  * Main: Contains Menu
  53.  */
  54. int main() 
  55. {
  56.     skiplist ss;
  57.     int choice, n;
  58.     while (1)
  59.     {
  60.         cout<<endl<<"-----------------------"<<endl;
  61.         cout<<endl<<"Operations on Skip list"<<endl;
  62.         cout<<endl<<"-----------------------"<<endl;
  63.         cout<<"1.Insert Element"<<endl;
  64.         cout<<"2.Delete Element"<<endl;
  65.         cout<<"3.Search Element"<<endl;
  66.         cout<<"4.Display List "<<endl;
  67.         cout<<"5.Exit "<<endl;
  68.         cout<<"Enter your choice : ";
  69.         cin>>choice;
  70.         switch(choice)
  71.         {
  72.         case 1:
  73.              cout<<"Enter the element to be inserted: ";
  74.              cin>>n;
  75.              ss.insert_element(n);
  76.              if(ss.contains(n))
  77.                  cout<<"Element Inserted"<<endl;
  78.              break;
  79.         case 2:
  80.              cout<<"Enter the element to be deleted: ";
  81.              cin>>n;
  82.              if(!ss.contains(n))
  83.              {
  84.                  cout<<"Element not found"<<endl;
  85.                  break;
  86.              }
  87.              ss.delete_element(n);
  88.              if(!ss.contains(n))
  89.                  cout<<"Element Deleted"<<endl;
  90.              break;
  91.         case 3:
  92.              cout<<"Enter the element to be searched: ";
  93.              cin>>n; 
  94.              if(ss.contains(n))
  95.                  cout<<"Element "<<n<<" is in the list"<<endl;
  96.              else
  97.                  cout<<"Element not found"<<endl;
  98.         case 4:
  99.              cout<<"The List is: ";
  100.              ss.display();
  101.              break;
  102.         case 5:
  103.              exit(1);
  104.              break;
  105.         default:
  106.              cout<<"Wrong Choice"<<endl;
  107.         }
  108.     }
  109.     return 0;
  110. }
  111.  
  112. /*
  113.  * Random Value Generator
  114.  */
  115. float frand() 
  116. {
  117.     return (float) rand() / RAND_MAX;
  118. }
  119.  
  120. /*
  121.  * Random Level Generator
  122.  */
  123. int random_level() 
  124. {
  125.     static bool first = true;
  126.     if (first) 
  127.     {
  128.         srand((unsigned)time(NULL));
  129.         first = false;
  130.     }
  131.     int lvl = (int)(log(frand()) / log(1.-P));
  132.     return lvl < MAX_LEVEL ? lvl : MAX_LEVEL;
  133. }
  134.  
  135. /*
  136.  * Insert Element in Skip List
  137.  */
  138. void skiplist::insert_element(int &value) 
  139. {
  140.     snode *x = header;	
  141.     snode *update[MAX_LEVEL + 1];
  142.     memset(update, 0, sizeof(snode*) * (MAX_LEVEL + 1));
  143.     for (int i = level;i >= 0;i--) 
  144.     {
  145.         while (x->forw[i] != NULL && x->forw[i]->value < value) 
  146.         {
  147.             x = x->forw[i];
  148.         }
  149.         update[i] = x; 
  150.     }
  151.     x = x->forw[0];
  152.     if (x == NULL || x->value != value) 
  153.     {        
  154.         int lvl = random_level();
  155.         if (lvl > level) 
  156.         {
  157.             for (int i = level + 1;i <= lvl;i++) 
  158.             {
  159.                 update[i] = header;
  160.             }
  161.             level = lvl;
  162.         }
  163.         x = new snode(lvl, value);
  164.         for (int i = 0;i <= lvl;i++) 
  165.         {
  166.             x->forw[i] = update[i]->forw[i];
  167.             update[i]->forw[i] = x;
  168.         }
  169.     }
  170. }
  171.  
  172. /*
  173.  * Delete Element from Skip List
  174.  */
  175. void skiplist::delete_element(int &value) 
  176. {
  177.     snode *x = header;	
  178.     snode *update[MAX_LEVEL + 1];
  179.     memset (update, 0, sizeof(snode*) * (MAX_LEVEL + 1));
  180.     for (int i = level;i >= 0;i--) 
  181.     {
  182.         while (x->forw[i] != NULL && x->forw[i]->value < value)
  183.         {
  184.             x = x->forw[i];
  185.         }
  186.         update[i] = x; 
  187.     }
  188.     x = x->forw[0];
  189.     if (x->value == value) 
  190.     {
  191.         for (int i = 0;i <= level;i++) 
  192.         {
  193.             if (update[i]->forw[i] != x)
  194.                 break;
  195.             update[i]->forw[i] = x->forw[i];
  196.         }
  197.         delete x;
  198.         while (level > 0 && header->forw[level] == NULL) 
  199.         {
  200.             level--;
  201.         }
  202.     }
  203. }
  204.  
  205. /*
  206.  * Display Elements of Skip List
  207.  */
  208. void skiplist::display() 
  209. {
  210.     const snode *x = header->forw[0];
  211.     while (x != NULL) 
  212.     {
  213.         cout << x->value;
  214.         x = x->forw[0];
  215.         if (x != NULL)
  216.             cout << " - ";
  217.     }
  218.     cout <<endl;
  219. }
  220.  
  221. /*
  222.  * Search Elemets in Skip List
  223.  */
  224. bool skiplist::contains(int &s_value) 
  225. {
  226.     snode *x = header;
  227.     for (int i = level;i >= 0;i--) 
  228.     {
  229.         while (x->forw[i] != NULL && x->forw[i]->value < s_value)
  230.         {
  231.             x = x->forw[i];
  232.         }
  233.     }
  234.     x = x->forw[0];
  235.     return x != NULL && x->value == s_value;
  236. }

$ g++ skip_list.cpp
$ a.out
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 7
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 9
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 3
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 5
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 6
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 5 - 6 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 2
Enter the element to be deleted: 20
Element not found
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 2
Enter the element to be deleted: 6
Element Deleted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 3
Enter the element to be searched: 20
Element not found
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 3
Enter the element to be searched: 7
Element 7 is in the list
The List is: 3 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 1
Enter the element to be inserted: 4
Element Inserted
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 4
The List is: 3 - 4 - 5 - 7 - 9
 
---------------------------------
 
Operations on Skip list
 
---------------------------------
1.Insert Element
2.Delete Element
3.Search Element
4.Display List 
5.Exit 
Enter your choice : 5
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.