前言
跳躍表(簡稱跳表)由美國計(jì)算機(jī)科學(xué)家William Pugh發(fā)明于1989年扔役。他在論文《Skip lists: a probabilistic alternative to balanced trees》中詳細(xì)介紹了跳表的數(shù)據(jù)結(jié)構(gòu)和插入刪除等操作丁侄。
跳表(SkipList，全稱跳躍表)是用于有序元素序列快速搜索查找的一個(gè)數(shù)據(jù)結(jié)構(gòu)睛琳，跳表是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，實(shí)質(zhì)就是一種可以進(jìn)行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引私杜，通過索引來實(shí)現(xiàn)快速查找号俐。跳表不僅能提高搜索性能泌豆，同時(shí)也可以提高插入和刪除操作的性能。它在性能上和紅黑樹吏饿，AVL樹不相上下踪危，但是跳表的原理非常簡單，實(shí)現(xiàn)也比紅黑樹簡單很多猪落。
跳躍表（Skip list）是有序鏈表的擴(kuò)展贞远，簡稱跳表，它在原有的有序鏈表上增加了多級索引笨忌，通過索引來實(shí)現(xiàn)快速查找蓝仲，實(shí)質(zhì)上是一種可以進(jìn)行二分查找的有序鏈表。
實(shí)際上官疲，跳躍表并不是簡單地通過奇偶次序建立索引的袱结，而是通過隨機(jī)技術(shù)實(shí)現(xiàn)的，因此也可以說它是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)途凫。假如跳躍表每一層的晉升概率都是 1/2垢夹，則最理想的索引就是在原始鏈表中每隔一個(gè)元素抽取一個(gè)元素作為一級索引。其實(shí)在原始鏈表中隨機(jī)選擇 n/2 個(gè)元素作為一級索引也可以维费，因?yàn)殡S機(jī)選擇的元素相對均勻果元，對查找效率來講影響不大。當(dāng)原始鏈表中元素?cái)?shù)量足夠大且抽取足夠隨機(jī)時(shí)犀盟，得到的索引是均勻的而晒。因此隨機(jī)選擇 n/2 個(gè)元素作為一級索引，隨機(jī)選擇 n/4 個(gè)元素作為二級索引且蓬，隨機(jī)選擇 n/8 個(gè)元素作為三級索引欣硼，以此類推，一直到頂層索引。我們可以通過索引來提升跳躍表的查找效率诈胜。
跳躍表不僅可以提高搜索性能豹障，還可以提高插入和刪除操作的性能。平衡二叉查找樹在進(jìn)行插入焦匈、刪除操作后需要多次調(diào)整平衡血公，而跳躍表完全依靠隨機(jī)技術(shù)，其性能和平衡二叉查找樹不相上下缓熟，但是原理非常簡單累魔。跳躍表是一種性能比較優(yōu)秀的動態(tài)數(shù)據(jù)結(jié)構(gòu)，Redis 中的有序集合 Sorted Set 和 LevelDB 中的 MemTable 都是采用跳躍表實(shí)現(xiàn)的够滑。
在這里你可以看到一些關(guān)鍵詞：鏈表(有序鏈表)垦写、索引、二分查找彰触。
回顧鏈表梯投，我們知道鏈表和順序表(數(shù)組)通常都是相愛相殺，成對出現(xiàn)况毅，各有優(yōu)劣分蓖。而鏈表的優(yōu)勢就是更高效的插入、刪除尔许。痛點(diǎn)就是查詢很慢很慢么鹤！每次查詢都是一種O(n)復(fù)雜度的操作，鏈表估計(jì)自己都?xì)獾南肟蘖??味廊。
這是一個(gè)帶頭結(jié)點(diǎn)的鏈表(頭結(jié)點(diǎn)相當(dāng)于一個(gè)固定的入口蒸甜，不存儲有意義的值)，每次查找都需要一個(gè)個(gè)枚舉毡们，相當(dāng)?shù)穆富剩覀兡懿荒苌晕?yōu)化一下，讓它稍微跳一跳呢衙熔？答案是可以的登颓，我們知道很多算法和數(shù)據(jù)結(jié)構(gòu)以空間換時(shí)間，我們在上面加一層索引红氯，讓部分節(jié)點(diǎn)在上層能夠直接定位到框咙，這樣鏈表的查詢時(shí)間近乎減少一半。
這樣痢甘，在查詢某個(gè)節(jié)點(diǎn)的時(shí)候，首先會從上一層快速定位節(jié)點(diǎn)所在的一個(gè)范圍塞栅，如果找到具體范圍向下然后查找代價(jià)很小者铜，當(dāng)然在表的結(jié)構(gòu)設(shè)計(jì)上會增加一個(gè)向下的索引(指針)用來查找確定底層節(jié)點(diǎn)。平均查找速度平均為O(n/2)。但是當(dāng)節(jié)點(diǎn)數(shù)量很大的時(shí)候作烟，它依舊很慢很慢愉粤。我們都知道二分查找是每次都能折半的去壓縮查找范圍，要是有序鏈表也能這么跳起來那就太完美了拿撩。沒錯(cuò)跳表就能讓鏈表擁有近乎的接近二分查找的效率的一種數(shù)據(jù)結(jié)構(gòu)衣厘，其原理依然是給上面加若干層索引，優(yōu)化查找速度压恒。
通過上圖你可以看到影暴，通過這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)對有序鏈表進(jìn)行查找都能近乎二分的性能。就是在上面維護(hù)那么多層的索引探赫，首先在最高級索引上查找最后一個(gè)小于當(dāng)前查找元素的位置型宙，然后再跳到次高級索引繼續(xù)查找，直到跳到最底層為止期吓，這時(shí)候以及十分接近要查找的元素的位置了(如果查找元素存在的話)早歇。由于根據(jù)索引可以一次跳過多個(gè)元素，所以跳查找的查找速度也就變快了讨勤。
對于理想的跳表，每向上一層索引節(jié)點(diǎn)數(shù)量都是下一層的1/2.那么如果n個(gè)節(jié)點(diǎn)增加的節(jié)點(diǎn)數(shù)量(1/2+1/4+…)<n晨另。并且層數(shù)較低潭千，對查找效果影響不大。但是對于這么一個(gè)結(jié)構(gòu)借尿，你可能會疑惑刨晴，這樣完美的結(jié)構(gòu)真的存在嗎？大概率不存在的路翻，因?yàn)樽鳛橐粋€(gè)鏈表狈癞，少不了增刪該查的一些操作。而刪除和插入可能會改變整個(gè)結(jié)構(gòu)茂契，所以上面的這些都是理想的結(jié)構(gòu)蝶桶，在插入的時(shí)候是否添加上層索引是個(gè)概率問題(1/2的概率)，在后面會具體講解掉冶。
跳表的增刪改查
上面稍微了解了跳表是個(gè)啥真竖，那么在這里就給大家談?wù)勌淼脑鰟h改查過程。在實(shí)現(xiàn)本跳表的過程為了便于操作厌小，我們將跳表的頭結(jié)點(diǎn)(head)的key設(shè)為int的最小值(一定滿足左小右大方便比較)恢共。
對于每個(gè)節(jié)點(diǎn)的設(shè)置，設(shè)置成SkipNode類璧亚，為了防止初學(xué)者將next向下還是向右搞混讨韭，直接設(shè)置right，down兩個(gè)指針。
class SkipNode<T>
{
int key;
T value;
SkipNode right,down;//右下個(gè)方向的指針
public SkipNode (int key,T value) {
this.key=key;
this.value=value;
}
}
跳表的結(jié)構(gòu)和初始化也很重要透硝，其主要參數(shù)和初始化方法為：
public class SkipList <T> {
SkipNode headNode;//頭節(jié)點(diǎn)吉嚣，入口
int highLevel;//當(dāng)前跳表索引層數(shù)
Random random;// 用于投擲硬幣
final int MAX_LEVEL = 32;//最大的層
SkipList(){
random=new Random();
headNode=new SkipNode(Integer.MIN_VALUE,null);
highLevel=0;
}
//其他方法
}
查詢操作
很多時(shí)候鏈表也可能這樣相連僅僅是某個(gè)元素或者key作為有序的標(biāo)準(zhǔn)。所以有可能鏈表內(nèi)部存在一些value蹬铺。不過修改和查詢其實(shí)都是一個(gè)操作尝哆，找到關(guān)鍵數(shù)字(key)。并且查找的流程也很簡單甜攀，設(shè)置一個(gè)臨時(shí)節(jié)點(diǎn)team=head秋泄。當(dāng)team不為null其流程大致如下：
- (1) 從team節(jié)點(diǎn)出發(fā)，如果當(dāng)前節(jié)點(diǎn)的key與查詢的key相等规阀，那么返回當(dāng)前節(jié)點(diǎn)(如果是修改操作那么一直向下進(jìn)行修改值即可)恒序。
- (2) 如果key不相等，且右側(cè)為null谁撼，那么證明只能向下(結(jié)果可能出現(xiàn)在下右方向)歧胁，此時(shí)team=team.down
- (3) 如果key不相等，且右側(cè)不為null厉碟，且右側(cè)節(jié)點(diǎn)key小于待查詢的key喊巍。那么說明同級還可向右，此時(shí)team=team.right
- (4)（否則的情況）如果key不相等箍鼓，且右側(cè)不為null崭参，且右側(cè)節(jié)點(diǎn)key大于待查詢的key 。那么說明如果有結(jié)果的話就在這個(gè)索引和下個(gè)索引之間款咖，此時(shí)team=team.down何暮。
- 最終將按照這個(gè)步驟返回正確的節(jié)點(diǎn)或者null(說明沒查到)。
例如上圖查詢12節(jié)點(diǎn)铐殃，首先第一步從head出發(fā)發(fā)現(xiàn)右側(cè)不為空海洼，且7<12,向右；第二步右側(cè)為null向下富腊；第三步節(jié)點(diǎn)7的右側(cè)10<12繼續(xù)向右坏逢；第四步10右側(cè)為null向下；第五步右側(cè)12小于等于向右蟹肘。第六步起始發(fā)現(xiàn)相等返回節(jié)點(diǎn)結(jié)束词疼。
而這塊的代碼也非常容易：
public SkipNode search(int key) {
SkipNode team=headNode;
while (team!=null) {
if(team.key==key) {
return team;
}
else if(team.right==null) { //右側(cè)沒有了，只能下降
team = team.down;
}
else if(team.right.key>key) { //需要下降去尋找
team = team.down;
}
else { //右側(cè)比較小向右
team = team.right;
}
}
return null;
}
刪除操作
刪除操作比起查詢稍微復(fù)雜一丟丟帘腹，但是比插入簡單贰盗。刪除需要改變鏈表結(jié)構(gòu)所以需要處理好節(jié)點(diǎn)之間的聯(lián)系。對于刪除操作你需要謹(jǐn)記以下幾點(diǎn)：
- (1)刪除當(dāng)前節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的前后節(jié)點(diǎn)都有關(guān)系
- (2)刪除當(dāng)前層節(jié)點(diǎn)之后阳欲，下一層該key的節(jié)點(diǎn)也要刪除舵盈，一直刪除到最底層
根據(jù)這兩點(diǎn)分析一下：如果找到當(dāng)前節(jié)點(diǎn)了陋率，它的前面一個(gè)節(jié)點(diǎn)怎么查找呢？這個(gè)總不能在遍歷一遍吧秽晚！有的使用四個(gè)方向的指針(上下左右)用來找到左側(cè)節(jié)點(diǎn)瓦糟。是可以的，但是這里可以特殊處理一下 赴蝇，不直接判斷和操作節(jié)點(diǎn)菩浙，先找到待刪除節(jié)點(diǎn)的左側(cè)節(jié)點(diǎn)。通過這個(gè)節(jié)點(diǎn)即可完成刪除句伶，然后這個(gè)節(jié)點(diǎn)直接向下去找下一層待刪除的左側(cè)節(jié)點(diǎn)劲蜻。設(shè)置一個(gè)臨時(shí)節(jié)點(diǎn)team=head，當(dāng)team不為null具體循環(huán)流程為：
- (1)如果team右側(cè)為null考余，那么team=team.down(之所以敢直接這么判斷是因?yàn)樽髠?cè)有頭結(jié)點(diǎn)在左側(cè)先嬉，不用擔(dān)心特殊情況)
- (2)如果team右側(cè)不 為null，并且右側(cè)的key等于待刪除的key楚堤，那么先刪除節(jié)點(diǎn)疫蔓，再team向下team=team.down為了刪除下層節(jié)點(diǎn)。
- (3)如果team右側(cè)不 為null身冬，并且右側(cè)key小于待刪除的key衅胀，那么team向右team=team.right。
- (4)如果team右側(cè)不 為null吏恭，并且右側(cè)key大于待刪除的key拗小，那么team向下team=team.down，在下層繼續(xù)查找刪除節(jié)點(diǎn)樱哼。
例如上圖刪除10節(jié)點(diǎn)，首先team=head從team出發(fā)剿配，7<10向右(team=team.right后面省略)搅幅；第二步右側(cè)為null只能向下；第三部右側(cè)為10在當(dāng)前層刪除10節(jié)點(diǎn)然后向下繼續(xù)查找下一層10節(jié)點(diǎn)呼胚；第四步8<10向右茄唐；第五步右側(cè)為10刪除該節(jié)點(diǎn)并且team向下。team為null說明刪除完畢退出循環(huán)蝇更。
刪除操作實(shí)現(xiàn)的代碼如下：
public void delete(int key) {//刪除不需要考慮層數(shù)
SkipNode team=headNode;
while (team!=null) {
if (team.right == null) {//右側(cè)沒有了沪编，說明這一層找到，沒有只能下降
team=team.down;
}
else if(team.right.key==key) {//找到節(jié)點(diǎn)年扩，右側(cè)即為待刪除節(jié)點(diǎn)
team.right=team.right.right;//刪除右側(cè)節(jié)點(diǎn)
team=team.down;//向下繼續(xù)查找刪除
}
else if(team.right.key>key) {//右側(cè)已經(jīng)不可能了蚁廓，向下
team=team.down;
}
else { //節(jié)點(diǎn)還在右側(cè)
team=team.right;
}
}
}
插入操作
插入操作在實(shí)現(xiàn)起來是最麻煩的，需要的考慮的東西最多厨幻∠嗲叮回顧查詢腿时，不需要動索引；回顧刪除饭宾，每層索引如果有刪除就是了而昨。但是插入不一樣了斑响，插入需要考慮是否插入索引，插入幾層等問題。由于需要插入刪除所以我們肯定無法維護(hù)一個(gè)完全理想的索引結(jié)構(gòu)准谚，因?yàn)樗馁M(fèi)的代價(jià)太高。但我們使用隨機(jī)化的方法去判斷是否向上層插入索引霎挟。即產(chǎn)生一個(gè)[0-1]的隨機(jī)數(shù)如果小于0.5就向上插入索引襟衰，插入完畢后再次使用隨機(jī)數(shù)判斷是否向上插入索引。運(yùn)氣好這個(gè)值可能是多層索引肤频，運(yùn)氣不好只插入最底層(這是100%插入的)叹括。但是索引也不能不限制高度，我們一般會設(shè)置索引最高值如果大于這個(gè)值就不往上繼續(xù)添加索引了宵荒。
我們一步步剖析該怎么做汁雷，其流程為
(1)首先通過上面查找的方式，找到待插入的左節(jié)點(diǎn)报咳。插入的話最底層肯定是需要插入的侠讯，所以通過鏈表插入節(jié)點(diǎn)(需要考慮是否為末尾節(jié)點(diǎn))
(2)插入完這一層，需要考慮上一層是否插入暑刃，首先判斷當(dāng)前索引層級厢漩，如果大于最大值那么就停止(比如已經(jīng)到最高索引層了)。否則設(shè)置一個(gè)隨機(jī)數(shù)1/2的概率向上插入一層索引(因?yàn)槔硐霠顟B(tài)下的就是每2個(gè)向上建一個(gè)索引節(jié)點(diǎn))岩臣。
(3)繼續(xù)(2)的操作溜嗜，直到概率退出或者索引層數(shù)大于最大索引層。
在具體向上插入的時(shí)候架谎，實(shí)質(zhì)上還有非常重要的細(xì)節(jié)需要考慮炸宵。首先如何找到上層的待插入節(jié)點(diǎn) ？
這個(gè)各個(gè)實(shí)現(xiàn)方法可能不同谷扣，如果有左土全、上指向的指針那么可以向左向上找到上層需要插入的節(jié)點(diǎn)，但是如果只有右指向和下指向的我們也可以巧妙的借助查詢過程中記錄下降的節(jié)點(diǎn)会涎。因?yàn)樵?jīng)下降的節(jié)點(diǎn)倒序就是需要插入的節(jié)點(diǎn)裹匙，最底層也不例外(因?yàn)闆]有匹配值會下降為null結(jié)束循環(huán))。在這里我使用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲末秃，當(dāng)然使用List也可以概页。下圖就是給了一個(gè)插入示意圖。
其次如果該層是目前的最高層索引蛔溃，需要繼續(xù)向上建立索引應(yīng)該怎么辦绰沥？
首先跳表最初肯定是沒索引的篱蝇，然后慢慢添加節(jié)點(diǎn)才有一層、二層索引徽曲，但是如果這個(gè)節(jié)點(diǎn)添加的索引突破當(dāng)前最高層零截，該怎么辦呢？
這時(shí)候需要注意了秃臣，跳表的head需要改變了涧衙，新建一個(gè)ListNode節(jié)點(diǎn)作為新的head，將它的down指向老head奥此，將這個(gè)head節(jié)點(diǎn)加入棧中(也就是這個(gè)節(jié)點(diǎn)作為下次后面要插入的節(jié)點(diǎn))弧哎，就比如上面的9節(jié)點(diǎn)如果運(yùn)氣夠好在往上建立一層節(jié)點(diǎn)，會是這樣的稚虎。
插入上層的時(shí)候注意所有節(jié)點(diǎn)要新建(拷貝)撤嫩，除了right的指向down的指向也不能忘記，down指向上一個(gè)節(jié)點(diǎn)可以用一個(gè)臨時(shí)節(jié)點(diǎn)作為前驅(qū)節(jié)點(diǎn)蠢终。如果層數(shù)突破當(dāng)前最高層序攘，頭head節(jié)點(diǎn)(入口)需要改變。
這部分更多的細(xì)節(jié)在代碼中注釋解釋了寻拂，詳細(xì)代碼為：
public void add(SkipNode node) {
int key=node.key;
SkipNode findNode=search(key);
if(findNode!=null) {//如果存在這個(gè)key的節(jié)點(diǎn)
findNode.value=node.value;
return;
}
Stack<SkipNode>stack=new Stack<SkipNode>();//存儲向下的節(jié)點(diǎn)程奠，這些節(jié)點(diǎn)可能在右側(cè)插入節(jié)點(diǎn)
SkipNode team=headNode;//查找待插入的節(jié)點(diǎn) 找到最底層的哪個(gè)節(jié)點(diǎn)。
while (team!=null) {//進(jìn)行查找操作
if(team.right==null) {//右側(cè)沒有了祭钉，只能下降
stack.add(team);//將曾經(jīng)向下的節(jié)點(diǎn)記錄一下
team=team.down;
}
else if(team.right.key>key) {//需要下降去尋找
stack.add(team);//將曾經(jīng)向下的節(jié)點(diǎn)記錄一下
team=team.down;
}
else {//向右
team=team.right;
}
}
int level=1;//當(dāng)前層數(shù)瞄沙，從第一層添加(第一層必須添加，先添加再判斷)
SkipNode downNode=null;//保持前驅(qū)節(jié)點(diǎn)(即down的指向慌核，初始為null)
while (!stack.isEmpty()) {
//在該層插入node
team=stack.pop();//拋出待插入的左側(cè)節(jié)點(diǎn)
SkipNode nodeTeam=new SkipNode(node.key, node.value);//節(jié)點(diǎn)需要重新創(chuàng)建
nodeTeam.down=downNode;//處理豎方向
downNode=nodeTeam;//標(biāo)記新的節(jié)點(diǎn)下次使用
if(team.right==null) {//右側(cè)為null 說明插入在末尾
team.right=nodeTeam;
}
//水平方向處理
else {//右側(cè)還有節(jié)點(diǎn)距境，插入在兩者之間
nodeTeam.right=team.right;
team.right=nodeTeam;
}
//考慮是否需要向上
if(level>MAX_LEVEL)//已經(jīng)到達(dá)最高級的節(jié)點(diǎn)啦
break;
double num=random.nextDouble();//[0-1]隨機(jī)數(shù)
if(num>0.5)//運(yùn)氣不好結(jié)束
break;
level++;
if(level>highLevel) {//比當(dāng)前最大高度要高但是依然在允許范圍內(nèi) 需要改變head節(jié)點(diǎn)
highLevel=level;
//需要創(chuàng)建一個(gè)新的節(jié)點(diǎn)
SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
highHeadNode.down=headNode;
headNode=highHeadNode;//改變head
stack.add(headNode);//下次拋出head
}
}
}
總結(jié)
對于上面，跳表完整分析就結(jié)束啦垮卓，當(dāng)然肮疗，你可能看到不同品種跳表的實(shí)現(xiàn)，還有的用數(shù)組方式表示上下層的關(guān)系這樣也可以扒接，但本文只定義right和down兩個(gè)方向的鏈表更純正化的講解跳表。
對于跳表以及跳表的同類競爭產(chǎn)品：紅黑樹们衙，為啥Redis的有序集合(zset) 使用跳表呢钾怔？因?yàn)樘沓瞬檎也迦刖S護(hù)和紅黑樹有著差不多的效率，它是個(gè)鏈表蒙挑，能確定范圍區(qū)間宗侦，而區(qū)間問題在樹上可能就沒那么方便查詢啦。而JDK中跳躍表ConcurrentSkipListSet和ConcurrentSkipListMap忆蚀。 有興趣的也可以查閱一下源碼矾利。
對于學(xué)習(xí)姑裂，完整的代碼是非常重要的，這里我把完整代碼貼出來男旗，需要的自取舶斧。
import java.util.Random;
import java.util.Stack;
class SkipNode<T> {
int key;
T value;
SkipNode right,down;//左右上下四個(gè)方向的指針
public SkipNode (int key,T value) {
this.key=key;
this.value=value;
}
}
public class SkipList <T> {
SkipNode headNode;//頭節(jié)點(diǎn)，入口
int highLevel;//層數(shù)
Random random;// 用于投擲硬幣
final int MAX_LEVEL = 32;//最大的層
SkipList(){
random=new Random();
headNode=new SkipNode(Integer.MIN_VALUE,null);
highLevel=0;
}
public SkipNode search(int key) {
SkipNode team=headNode;
while (team!=null) {
if(team.key==key){
return team;
}
else if(team.right==null) { //右側(cè)沒有了察皇，只能下降
team=team.down;
}
else if(team.right.key>key) { //需要下降去尋找
team=team.down;
}
else { //右側(cè)比較小向右
team=team.right;
}
}
return null;
}
public void delete(int key) { //刪除不需要考慮層數(shù)
SkipNode team=headNode;
while (team!=null) {
if (team.right == null) { //右側(cè)沒有了茴厉，說明這一層找到，沒有只能下降
team=team.down;
}
else if(team.right.key==key) { //找到節(jié)點(diǎn)什荣，右側(cè)即為待刪除節(jié)點(diǎn)
team.right=team.right.right;//刪除右側(cè)節(jié)點(diǎn)
team=team.down;//向下繼續(xù)查找刪除
}
else if(team.right.key>key) { //右側(cè)已經(jīng)不可能了矾缓，向下
team=team.down;
}
else { //節(jié)點(diǎn)還在右側(cè)
team=team.right;
}
}
}
public void add(SkipNode node) {
int key=node.key;
SkipNode findNode=search(key);
if(findNode!=null) { //如果存在這個(gè)key的節(jié)點(diǎn)
findNode.value=node.value;
return;
}
Stack<SkipNode>stack=new Stack<SkipNode>();//存儲向下的節(jié)點(diǎn)，這些節(jié)點(diǎn)可能在右側(cè)插入節(jié)點(diǎn)
SkipNode team=headNode;//查找待插入的節(jié)點(diǎn) 找到最底層的哪個(gè)節(jié)點(diǎn)稻爬。
while (team!=null) {//進(jìn)行查找操作
if(team.right==null) { //右側(cè)沒有了嗜闻，只能下降
stack.add(team);//將曾經(jīng)向下的節(jié)點(diǎn)記錄一下
team=team.down;
}
else if(team.right.key>key) { //需要下降去尋找
stack.add(team);//將曾經(jīng)向下的節(jié)點(diǎn)記錄一下
team=team.down;
}
else { //向右
team=team.right;
}
}
int level=1;//當(dāng)前層數(shù)，從第一層添加(第一層必須添加桅锄，先添加再判斷)
SkipNode downNode=null;//保持前驅(qū)節(jié)點(diǎn)(即down的指向琉雳，初始為null)
while (!stack.isEmpty()) {
//在該層插入node
team=stack.pop();//拋出待插入的左側(cè)節(jié)點(diǎn)
SkipNode nodeTeam=new SkipNode(node.key, node.value);//節(jié)點(diǎn)需要重新創(chuàng)建
nodeTeam.down=downNode;//處理豎方向
downNode=nodeTeam;//標(biāo)記新的節(jié)點(diǎn)下次使用
if(team.right==null) {//右側(cè)為null 說明插入在末尾
team.right=nodeTeam;
}
//水平方向處理
else {//右側(cè)還有節(jié)點(diǎn)，插入在兩者之間
nodeTeam.right=team.right;
team.right=nodeTeam;
}
//考慮是否需要向上
if(level>MAX_LEVEL)//已經(jīng)到達(dá)最高級的節(jié)點(diǎn)啦
break;
double num=random.nextDouble();//[0-1]隨機(jī)數(shù)
if(num>0.5)//運(yùn)氣不好結(jié)束
break;
level++;
if(level>highLevel) { //比當(dāng)前最大高度要高但是依然在允許范圍內(nèi) 需要改變head節(jié)點(diǎn)
highLevel=level;
//需要創(chuàng)建一個(gè)新的節(jié)點(diǎn)
SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
highHeadNode.down=headNode;
headNode=highHeadNode;//改變head
stack.add(headNode);//下次拋出head
}
}
}
public void printList() {
SkipNode teamNode=headNode;
int index=1;
SkipNode last=teamNode;
while (last.down!=null){
last=last.down;
}
while (teamNode!=null) {
SkipNode enumNode=teamNode.right;
SkipNode enumLast=last.right;
System.out.printf("%-8s","head->");
while (enumLast!=null&&enumNode!=null) {
if(enumLast.key==enumNode.key) {
System.out.printf("%-5s",enumLast.key+"->");
enumLast=enumLast.right;
enumNode=enumNode.right;
}
else {
enumLast=enumLast.right;
System.out.printf("%-5s","");
}
}
teamNode=teamNode.down;
index++;
System.out.println();
}
}
public static void main(String[] args) {
SkipList<Integer>list=new SkipList<Integer>();
for(int i=1;i<20;i++) {
list.add(new SkipNode(i,666));
}
list.printList();
list.delete(4);
list.delete(8);
list.printList();
}
}
進(jìn)行測試一下可以發(fā)現(xiàn)跳表還是挺完美的竞滓。
參考：
https://www.cnblogs.com/bigsai/p/14193225.html
https://www.jb51.net/article/271068.htm
https://zhuanlan.zhihu.com/p/651419093
