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 List, findEntry(k) will return the reference to the entry containg the key k
      • If the key k is not found in the Skip List, findEntry(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 height: repeat 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 entry: right 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 p, scan 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 entry: right 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

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/davidwang456/p/3620957.html