跳躍鏈表及其應用是非常熱門的問題，面試時也非常常問，深入了解其中奧秘大有裨益，不吹了，直接開始！

跳躍鏈表的基本概念

初識跳表

跳躍列表是一種數(shù)據結構。它允許快速查詢一個有序連續(xù)元素的數(shù)據鏈表。跳躍列表的平均查找和插入時間復雜度都是O(log n)，優(yōu)于普通隊列的O(n)。

跳躍列表由威廉·普發(fā)明，發(fā)明者對跳躍列表的評價：跳躍鏈表是在很多應用中有可能替代平衡樹而作為實現(xiàn)方法的一種數(shù)據結構。

跳躍列表的算法有同平衡樹一樣的漸進的預期時間邊界，并且更簡單、更快速和使用更少的空間。

這種數(shù)據結構是由William Pugh(音譯為威廉·普)發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。

我在谷歌上找到一篇作者關于跳表的論文，感興趣強烈建議下載閱讀：

https://epaperpress.com/sortsearch/download/skiplist.pdf

看下這篇論文的摘要部分：

從中我們獲取到的信息是：跳表在動態(tài)查找過程中使用了一種非嚴格的平衡機制來讓插入和刪除都更加便利和快捷，這種非嚴格平衡是基于概率的，而不是平衡樹的嚴格平衡。

說到非嚴格平衡，首先想到的是紅黑樹RbTree，它同樣采用非嚴格平衡來避免像AVL那樣調整樹的結構，這里就不展開講紅黑樹了，看來跳表也是類似的路子，但是是基于概率實現(xiàn)的。

動態(tài)查找的數(shù)據結構

所謂動態(tài)查找就是查找的過程中存在元素的刪除和插入，這樣就對實現(xiàn)查找的數(shù)據結構有一定的挑戰(zhàn)，因為在每次刪除和插入時都要調整數(shù)據結構，來保持秩序。

可以作為查找數(shù)據結構的包括：

• 線性結構：數(shù)組、鏈表
• 非線性結構：平衡樹

來分析一下各種數(shù)據結構在應對動態(tài)查找時的優(yōu)劣吧！

數(shù)組結構

數(shù)組結構簡單內存連續(xù)，可以實現(xiàn)二分查找等基于下標的操作，我一直認為數(shù)組的殺手锏就是下標，連續(xù)的內存也帶來了問題。

當進行插入和刪除時就面臨著整體的調整，就像在火車站排隊買票，隊頭走一個整個隊伍向前挪一步，有加塞的后面的又整體向后挪一步，這種整體移動操作在數(shù)組結構中性能損耗很大，并且在大數(shù)據量時對連續(xù)內存要求很高，當然這個在大內存機器上可能沒有什么問題。

如圖插入6和刪除5時 數(shù)組元素的移動：

鏈表結構

鏈表結構也比較簡單，但是不要求內存連續(xù)，不連續(xù)也就沒有下標可以加速，但是鏈表在執(zhí)行刪除和插入時影響的只是插入刪除點的前后元素，影響非常小。

但是每次查找元素是需要進行遍歷，就算我知道某個元素一定在大致的什么位置，也只能一步步走過去，看到這里要覺得有優(yōu)化的空間，那你也蠻厲害的了，說不定早幾年跳表就是你的發(fā)明了。

如圖刪除元素5和插入元素49時的處理：

平衡樹

平衡樹也是處理動態(tài)查找問題的一把好手，樹一般是基于鏈表實現(xiàn)的，只不過樹的節(jié)點之間并不是鏈表簡單的線性關系，會有兄弟姐妹父親等節(jié)點，并且各個層級有數(shù)量的限制，可以看到樹其實還是蠻復雜的。

節(jié)點需要存儲的信息很多，各個指針指來指去，復雜的結構增加了調整平衡性的難度，不同情況下的左旋右旋，所以出現(xiàn)了紅黑樹這種工程版本的AVL，但是在實際場景中可能并不需要這些兄弟姐妹父親關系，有種殺雞宰牛刀的意味了。

紅黑樹的節(jié)點結構定義：

#define?COLOR_RED??0x0
#define?COLOR_BLACK?0x1

typedef?struct?RBNode{
???int?key;
???unsigned?char?color;
???struct?RBNode?*left;
???struct?RBNode?*right;
???struct?RBNode?*parent;
}rb_node_t,?*rb_tree_t;
另外紅黑樹調整屬性過程中插入分為3種情況，刪除分為4種情況，還是比較難以理解的，除非你穿紅上衣