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)                                                 
    • SkipListEntry.java Prog file: click here
    • SkipList.java Prog file: click here
    • Test program 1 (inserts 4 entries): click here
    • Test program 2 (inserts 40 entries): click here

    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

最新文章

1. 基于Qt5.5.0的sql数据库、SDK_tts文本语音朗读的CET四六级单词背诵系统软件的编写V1.0
2. （转）分布式深度学习系统构建 简介 Distributed Deep Learning
3. BZOJ 3434 时空穿梭
4. Checking For User Permissions Before Updating or Inserting The Records in Oracle Forms
5. SqlParameter设定的value值为0时、调用的存储过程获取到的值却为null解决方法
6. 无限大整数相加算法的C语言源代码
7. axure母版（模板）区域介绍
8. javascript中apply,call,bind区别，bind兼容等问题总结
9. boost::this_thread::sleep_for()死锁
10. Python configparser 读取指定节点内容失败
11. pypinyin, jieba分词与Gensim
12. mysql函数调用过程
13. Linux telnet安装
14. 传统D3D11程序面向VS2015编译环境的配置修正细节
15. JAVA_模糊查询_重点是concat关键字
16. Java设计模式学习记录-抽象工厂模式
17. bzoj千题计划186：bzoj1048: [HAOI2007]分割矩阵
18. PHP读取超大日志文件
19. 程序媛计划——python初级课时1~2
20. 从源码分析StringUtils包

热门文章

1. C++实现网格水印之调试笔记（六）—— 提取完成
2. C++实现网格水印之调试笔记（二）
3. 通过库函数API和C代码中嵌入汇编代码剖析系统调用的工作机制
4. leetcode&mdash;sqrt
5. sf空间配置
6. &lt;问题&gt;Eclipse中Deploy应用到GAE的错误
7. hdu5909-Tree Cutting（树形dp）
8. 启动程序的同时传参给接收程序（XE8+WIN764）
9. Spring Autowiring by Type
10. C/C++ 不带参数的回调函数 与 带参数的回调函数 函数指针数组 例子