一、跳躍鏈表的構(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)。