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

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

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

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

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

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

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

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

延伸閱讀：

二、跳表（Skip List）是什么

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

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

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

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

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