Implementing the skip list data structure in java --reference

reference:http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html

  • The link list element structure used to implement a Skip List

     

    • The link list element used to implement the skip list has 4 links (not including the data portion):

       

       

     





     

  • The Entry strcuture in a Skip List (the SkipListEntry class)

     

    • Skip List entry:

       

        public class SkipListEntry
        {
           public String key;
           public Integer value;
      
           public SkipListEntry up;       // up link
           public SkipListEntry down;     // down link
           public SkipListEntry left;     // left link
           public SkipListEntry right;    // right link        
             
           ...
           (methods)
        }
      

       


      Note:

       

      • As you can see, my entry type is again very specific (no generic types):

         

        • String key
        • Integer value             

         


         

      • When I write the demo program, I will do it using specific types (classes)not parameterized classes

        I have showed you how to convert a specific class into a parameterized class, so you can write one if you want to

         


         

      • Reason for using specific classes:

         

        • My choice is didactic in nature; I don‘t want to spend time analyzing the overly complex syntax of parameterized classes

           

        • I want to spend my time teaching algorithms, not Java syntax

         

       

     



     



     

  • Making (and using) the special ?∞ and +∞ elements

     

    • Representing the ?∞ element and the +∞ element:

       

      • The ?∞ and the +∞ is just an ordinary Skip List Entry containing a special value for the key field.

       


       

    • We can accommodate the ?∞ element and the +∞ element by defining 2 special key value:

       

        public class SkipListEntry
        {
           public String key;						     
           public Integer value;						     
      
           public SkipListEntry up, down, left, right;			     
        									
           public static String negInf = "-oo";  // -inf key value
           public static String posInf = "+oo";  // +inf key value
         
         
           ....
        }
      

       


       

    • How to instantiate a Skip List entry containing +∞:

       

           SkipListEntry x = new SkipListEntry( SkipListEntry.posInf, null );      
      

      How to check if an Skip List entry x contains +∞:

       

             key == SkipListEntry.posInf             
      

     





    OK, now we move on to the Skip list itself....

     





     

  • Structure (class) to represent a Skip List

     

    • Remember that a Skip List is a very complicated list

      But.... It is never the less a list

       

      • To represent a list, we only use a pointer (that points to the first element)

         

      • Often, we use more pointers for improve efficiency (such as a tail pointer)

       


       

    • Variables in the SkipList class:

       

         public class SkipList
         {
           public SkipListEntry head;    // First element of the top level
           public SkipListEntry tail;    // Last element of the top level
          
          
           public int n;                 // number of entries in the Skip List   
          
           public int h;       // Height
           public Random r;    // Coin toss
          
           ....
          
         }
      

      Note:

       

      • The Random object r is used to determine the height of a newly added entry           

        (We use r to simulate a coin toss experiment)

       

       


       

    • Example illustrating how the variables are used:

       

      Note:

       

      • Since the logical top level does not contain any entries:

         

        • The implementation will omit the logical top layer

         

         


         

      • The variables head and tail provide quick access to the end elements of the real top layer

        Usage of head and tail:

         

        • They allow us to easily add an new layer above the top layer

         

       

     





     

  • Constructing a Skip List object

     

    • The constructor will construct an empty Skip List which looks like this:

       

       

    • Constructor code:

       

        public SkipList()     // Constructor...
        {
           SkipListEntry p1, p2;
      
           /* -----------------------------------
              Create an -oo and an +oo object
      	----------------------------------- */
           p1 = new SkipListEntry(SkipListEntry.negInf, null);
           p2 = new SkipListEntry(SkipListEntry.posInf, null);
      
      
           /* --------------------------------------
              Link the -oo and +oo object together
      	--------------------------------------- */
           p1.right = p2;
           p2.left = p1;
      
           /* --------------------------------------
              Initialize "head" and "tail"
      	--------------------------------------- */
           head = p1;
           tail = p2;
      
           /* --------------------------------------
              Other initializations
      	--------------------------------------- */
           n = 0;                   // No entries in Skip List
           h = 0;		      // Height is 0
      
           r = new Random();	      // Make random object to simulate coin toss
        }
      

       


       

    • The SkipList class so far:

       

         public class SkipList
         {
           public SkipListEntry head;    // First element of the top level
           public SkipListEntry tail;    // Last element of the top level
          
           public int n;                 // number of entries in the Skip List    
          
           public int h;       // Height
           public Random r;    // Coin toss
          
           public SkipList()    // Constructor...
           {
         	SkipListEntry p1, p2;
          
         	p1 = new SkipListEntry(SkipListEntry.negInf, null);
         	p2 = new SkipListEntry(SkipListEntry.posInf, null);
          
         	head = p1;
         	tail = p2;
          
         	p1.right = p2;
         	p2.left = p1;
          
         	n = 0;
          
         	h = 0;
         	r = new Random();
           }
          
           ...
         }
      

       

     



     



     

  • Implementing the basic Map operations

     

    • Basic Map operations:

       

      • get()
      • put()
      • remove()            

      Notice that each basic operation must first find (search) the appropriate entry (using a key) before the operation can be completed.

      So we must learn how to search a Skip List for a given key first....

       

     



     



     

  • Search operation in a skip list

     

    • Consider the links traversed to locate the key 50:

       

       


       

    • Psuedo code:

       

      
         p = head;
      
         repeat
         {
      
            Move to the right until your right neighbor node         
            contains a key that is greater than k     
      
            if ( not lowest level )
               Drop down one level
            else
               exit
         }
      
      

       

       


       

    • Search algorithm for Skip List:

       

      
        /* ------------------------------------------------------
           findEntry(k): find the largest key x <= k
                         on the LOWEST level of the Skip List
           ------------------------------------------------------ */
      
        public SkipListEntry findEntry(String k)
        {
           SkipListEntry p;
      
           /* -----------------
              Start at "head"
              ----------------- */
           p = head;
      
           while ( true )
           {
              /* ------------------------------------------------
                 Search RIGHT until you find a LARGER entry
      
                 E.g.: k = 34
      
                           10 ---> 20 ---> 30 ---> 40
                                            ^
                                            |
                                            p must stop here
      		p.right.key = 40
                 ------------------------------------------------ */           
              while ( (p.right.key) != SkipListEntry.posInf &&
                      (p.right.key).compareTo(k) <= 0 )
              {
                 p = p.right;         // Move to right
              }
      
              /* ---------------------------------
                 Go down one level if you can...
                 --------------------------------- */
              if ( p.down != null )
              {  
                 p = p.down;          // Go downwards
              }
              else
      	{
                 break;       // We reached the LOWEST level... Exit...
              }
           }
      
           return(p);         // Note: p.key <= k
        }
      


       

    • Note:

       

      • If the key k is found in the Skip ListfindEntry(k) will return the reference to the entry containg the key k

         


         

      • If the key k is not found in the Skip ListfindEntry(k) will return the reference to the floorEntry(k) entry containg a key that issmaller than k

        Example: findEntry(42) will return the reference to 39:

         

         

       

     





     

  • Implementing the "get(Key k)" method

     

    • get(k):

       

        /** Returns the value associated with a key. */               
      
        public Integer get (String k)
        {
           SkipListEntry p;
      
           p = findEntry(k);
      
           if ( k.equals( p.key ) )
              return(p.value);
           else
              return(null);
        }
      

       

     



     



     



     



     

  • Put(k,v): inserting into a Skip List

     

    • Pseudo code for put(k,v):

       

          put(k, v)
          {
             SkipListEntry p;
      
             p = findEntry(k);
      
             if ( k.equals( p.key ) )    // Found !
             {
                p.value = v;             // Update the value
      	  return;                  // Done
             }
      
             /* ==================================================
                Not found.
      
      	  Then:   p == floorEntry(k) !!!
      	  ================================================== */       
      
             (1) insert (k,v)  AFTER  p
             (2) make a column of (k,v) of RANDOM height
          }
      

       



       

    • Recall what happens when we insert a new entry:

       

      • Before insertion:

         

         


         

      • After inserting key 42:

         

        Note:

         

        • As part of the insert operation, we will make a column (see figure above) for that key

           


           

        • The height of the column will be random...

          (We have also seen how to use a random "trial" to generate a random height)

       



       

    • Step-by-step depictions of the steps necessary for insertion: put("42", ??)

       

      • Before the insertion:

         

         


         

      • Step 1: find the insert position

         

        p = findEntry(k)

         


         

      • Step 2: insert q after p:

         

         





         

      • Now make a column of random heightrepeat these steps a random number of times

         

         

        • Starting at p, (using p to) scan left and find the first entry that has an up-entry:

           

          Make p point to the up-element:

           



           

        • Create a new entry with the same key (we are making the "tower"):

           

           


           

        • Insert the newly created entryright of p and up from q:

           

           


           

        • Make q point to the newly inserted entry (to continue the iteration if necessay)

           

         


         

      • I will repeat the steps and show the effect of building a "tower":

         

         

        • Starting at pscan left and find the first entry that has an up-element:

           

           


           

        • Create a new entry (we are making another level of the "tower"):

           

           


           

        • Insert the newly created entryright of p and up from q:

           

           


           

        • Make q point to the newly inserted entry (to continue the iteration if necessay)

           

          (And so on)

           

         

       


       

    • Note:

       

      • If the height of the "tower" is = h:

         

        we must add an new empty layer before we can insert another entry:

         

         

     





     

  • Adding a (empty) layer

     

    • Before we can do anything, We need to what are the changes in the Skip List when we add an empty layer to the Skip List:

       

      • Here is the Skip List before we add a new (empty) top layer:

         

         


         

      • Here is the Skip List before we add a new (empty) top layer:

         

         

       

       


       

    • Add layer algorithm:

       

         SkipListEntry p1, p2;
      
         /* -----------------------------
            Make the -oo and +oo entries
            ---------------------------- */
         p1 = new SkipListEntry(SkipListEntry.negInf, null);        
         p2 = new SkipListEntry(SkipListEntry.posInf, null);
      
         /* --------------------
            Link them
            -------------------- */
         p1.right = p2;
         p1.down  = head;
      
         p2.left = p1;
         p2.down = tail;
      
         head.up = p1;
         tail.up = p2;
      
         /* --------------------
            Update head and tail
            -------------------- */
         head = p1;
         tail = p2;
      
         h = h + 1;         // One more level...
      

       

     



     



     



     

  • The put() method

     

     

    • put(k,v) psuedo code:

       

      
           p = findEntry(k);         // Find insert location
      
           if ( entry found )
           {
              update the value in p;
      	exit;
           }
      
           /* ----------------------------------
              Insert a brand new entry (k,v)
      
                   p   put q here   
                   |     |
                   V     V
                  [ ] <------> [ ]
      	---------------------------------- */
      
            q = new Entry(k,v);            // Make new entry
            link q after p;
      
            /* ------------------------
               Make a random tower...
      	 ------------------------ */
            while ( random() < 0.5 /* coin toss */ )
            {
               if ( height of tower >= h )
      	 {
      	    create a new TOP layer (see: click here)
               }
      
      	 p = Find the first left element in the next level above;       
      
      	 q = new Entry(k,v);
      	 link q after p;
            }
      

       

       




       

    • The put() method for Skip List in Java:

       

        public Integer put (String k, Integer v)
        {
           SkipListEntry p, q;
           int       i;
      
           p = findEntry(k);                  // Try find the entry
      
           /* ------------------------
              Check if key is found
              ------------------------ */
           if ( k.equals(p.key) )  // If key found, update the value and we are done...
           {
              Integer old = p.value;         // Remember the old value
      
              p.value = v;                   // Update value
      
              return(old);		       // Return the old value
           }
      
           /* -------------------------------------------------------------
              Key k is not found, then p = floorEntry(k) (See: click here)
      
              The rest of the code will insert a new entry (k,v)
              ------------------------------------------------------------- */
      
           q = new SkipListEntry(k,v);       // Create a new entry with k and v   
      
           /* --------------------------------------------------------------
              Insert q into the lowest level after SkipListEntry p:
      
                               p   put q here           p        q
                               |     |                  |        |
      		         V     V                  V        V        V
              Lower level:    [ ] <------> [ ]    ==>  [ ] <--> [ ] <--> [ ]
              --------------------------------------------------------------- */
           q.left = p;
           q.right = p.right;
           p.right.left = q;
           p.right = q;
      
           /* -----------------------------------------------------
              Make a "tower" of the entry e or RANDOM height
      	----------------------------------------------------- */
      
           i = 0;                   // Current level = 0
      
           while ( r.nextDouble() < 0.5 /* Coin toss */ )
           {
              // Coin toss success ! ---> build one more level !!!
      
              /* -------------------------------------------------------------------
      	   Check if we need to increase the height of the -oo and +oo "pillars
      	   ------------------------------------------------------------------- */
              if ( i >= h )   // We reached the top level !!!
              {
                 Create a new empty TOP layer (see: click here)
                 (Put the code from above here.... I left it out for brevity)
              }
      
              /* ------------------------------------
                 Find first element with an UP-link
                 ------------------------------------ */
              while ( p.up == null )
              {
                 p = p.left;
              }
      
      	/* --------------------------------
      	   Make p point to this UP element
      	   -------------------------------- */
              p = p.up;
      
      	/* ---------------------------------------------------
                 Add one more (k,*) to the column
      
      	   Schema for making the linkage:
      
                      p <--> e(k,*) <--> p.right
                                ^
      		          |
      		          v
      		          q
      	   ---------------------------------------------------- */
         	SkipListEntry e;
         		 
         	e = new SkipListEntry(k, null);  // Don‘t need the value...
         		 
         	/* ---------------------------------------
         	   Initialize links of e
         	   --------------------------------------- */
         	e.left = p;
         	e.right = p.right;
         	e.down = q;
         		 
         	/* ---------------------------------------
         	   Change the neighboring links..
         	   --------------------------------------- */
         	p.right.left = e;
         	p.right = e;
         	q.up = e;
      
              q = e;       // Set q up for next iteration (if there is one)
                           // See here for more detail: click here
      
              i = i + 1;   // Current level increases by one
           }
      
           n = n + 1;      // One more entry in the Skip List
      
           return(null);   // No old value
        }
      

       


       

    • Example Program: (Demo above code)                                                 

       

      Example output: (The keys are strings)

       

       -  -  -  -  -  -  -  -  -  -
       10
       13
       15 15
       2
       21
       25
       31 31 31
       33 33 33 33 33 33 33 33 33 33
       36
       38
       39 39 39 39 39
       41 41 41
       42 42 42 42
       5 5 5
       54 54
       57
       59 59 59 59 59 59 59
       60 60
       63 63
       65
       69
       7
       71 71 71 71 71
       72
       77 77
       81
       82
       86
       88
       90
       92 92
       99
       +  +  +  +  +  +  +  +  +  +         
      

       

     





     

  • Deleting an entry from a Skip List

     

    • What you must do to the skip list to remove an entry:

       

      • Before deletinng the entry 25:

         

         


         

      • After deleting the entry 25:

         

        (The whole column containing entries for 25 must be deleted !!!)

         

       




       

    • Step-by-step to accomplish: remove(25)

       

      • Before the deletion:

         

         


         

      • Step 1: locate the desired element (at the lowest level of the skip list):

         

         


         

      • While p != null, repeat these steps to remove the column:

         

        • Unlink the element at p (by making the left neighbor and the right neighbor pointing to each other)

           

           


           

        • Move p upward (prepare for loop)

           

         



         

      • Result of removal:

         

         

       

     





     

  • The Removal Algorithm

     

    • Psuedo code:

       

         p = findExntry(k);
      
         if (p.key != k)
           return(null);     // Not found, don‘t remove
      
         /* ------------------------------------------------------------
            We are at level 0
            Travel up the tower and link the left and right neighbors
            ------------------------------------------------------------ */        
         while ( p != null )
         {
            p.left.right = p.right;
            p.right.left = p.left;
         }
      

       


      补充,jdk中有一个java.util.concurrent.ConcurrentSkipListMap,可以参考这个skiplist实现。

    • * @author Doug Lea
      * @param <K> the type of keys maintained by this map
      * @param <V> the type of mapped values
      * @since 1.6

Implementing the skip list data structure in java --reference,古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。