一、跳躍鏈表的構(gòu)建思路

跳表一般基于有序鏈表實現(xiàn)。首先是鏈表的排序問題，對于鏈表的來說，排序的問題其實等價于怎么找到新增節(jié)點的在有序鏈表中插入位置。

對于數(shù)組而言，只需要利用二分法查找到對應(yīng)的位置，然后插入，并移動之后的元素，主要的開銷在于拓展內(nèi)存以及移動元素。

鏈表沒法這么處理。鏈表的優(yōu)勢在于插入后無需移動后續(xù)元素，但無法跳躍查詢，主要開銷在于定位插入位置。

結(jié)合兩者實際上就是跳表的基本思想：底層數(shù)據(jù)用有序鏈表維護(hù)，方便數(shù)據(jù)插入；在底層數(shù)據(jù)節(jié)點之上構(gòu)建多層不同的稀疏索引（比如從上往下不斷變密集），加速節(jié)點的查詢，快速定位。

索引節(jié)點+數(shù)據(jù)節(jié)點就是跳表的核心，但這又有了另一個問題：怎么樣便利的維護(hù)索引節(jié)點？

顯然，將每層的分區(qū)的中點作為索引節(jié)點是不合適的，因為節(jié)點的增減是一種常見需求，每次數(shù)據(jù)節(jié)點的增減都會導(dǎo)致索引節(jié)點的變化，帶來不少額外的開銷。我們需要一種與數(shù)據(jù)節(jié)點數(shù)量無關(guān)的、確定索引節(jié)點位置的方法。

基本的思路就是使用隨機(jī)化。在每次增加節(jié)點時確定是否需要此節(jié)點上建立索引節(jié)點。

延伸閱讀：

二、跳表（Skip List）是什么

跳表（Skip List）是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，它允許快速地查找、插入和刪除元素，其時間復(fù)雜度為O(log n)。

在跳表中，每個節(jié)點都有多個指針，這些指針分別指向同一層中的其他節(jié)點，具體地說，每個節(jié)點有一個指向下一個節(jié)點的指針，還有一個或多個指向下一層節(jié)點的指針。這些指針可以幫助我們在查找時跳過一些節(jié)點，從而減少查找的時間。

跳表中的節(jié)點通常按照升序排列，最底層的節(jié)點包含所有元素。每個節(jié)點還有一個隨機(jī)的層數(shù)，用來確定它在哪些層中有指針。一般來說，每個節(jié)點的層數(shù)都是隨機(jī)生成的，但是要滿足一定的概率分布。這樣可以確保跳表的高度不會太高，從而保證其時間復(fù)雜度的性能。

在跳表中，查找、插入和刪除操作都是基于每個節(jié)點的指針進(jìn)行的。具體來說，查找操作從較高層開始，按照升序查找節(jié)點，如果當(dāng)前節(jié)點的下一個節(jié)點的值比要查找的值大，則跳到下一層，繼續(xù)查找，直到找到目標(biāo)節(jié)點或者到達(dá)最底層。插入和刪除操作也是類似的，只需要在查找到目標(biāo)節(jié)點后，修改其指針即可。

總之，跳表是一種簡單而高效的數(shù)據(jù)結(jié)構(gòu)，可以在O(log n)的時間復(fù)雜度內(nèi)進(jìn)行查找、插入和刪除操作。雖然它在實際應(yīng)用中并不像紅黑樹那樣廣泛使用，但在某些場景下，跳表可以提供比其他數(shù)據(jù)結(jié)構(gòu)更好的性能表現(xiàn)。