一、跳躍鏈表的構建思路
跳表一般基于有序鏈表實現。首先是鏈表的排序問題,對于鏈表的來說,排序的問題其實等價于怎么找到新增節點的在有序鏈表中插入位置。
對于數組而言,只需要利用二分法查找到對應的位置,然后插入,并移動之后的元素,主要的開銷在于拓展內存以及移動元素。
鏈表沒法這么處理。鏈表的優勢在于插入后無需移動后續元素,但無法跳躍查詢,主要開銷在于定位插入位置。
結合兩者實際上就是跳表的基本思想:底層數據用有序鏈表維護,方便數據插入;在底層數據節點之上構建多層不同的稀疏索引(比如從上往下不斷變密集),加速節點的查詢,快速定位。
索引節點+數據節點就是跳表的核心,但這又有了另一個問題:怎么樣便利的維護索引節點?
顯然,將每層的分區的中點作為索引節點是不合適的,因為節點的增減是一種常見需求,每次數據節點的增減都會導致索引節點的變化,帶來不少額外的開銷。我們需要一種與數據節點數量無關的、確定索引節點位置的方法。
基本的思路就是使用隨機化。在每次增加節點時確定是否需要此節點上建立索引節點。
延伸閱讀:
二、跳表(Skip List)是什么
跳表(Skip List)是一種基于鏈表的數據結構,它允許快速地查找、插入和刪除元素,其時間復雜度為O(log n)。
在跳表中,每個節點都有多個指針,這些指針分別指向同一層中的其他節點,具體地說,每個節點有一個指向下一個節點的指針,還有一個或多個指向下一層節點的指針。這些指針可以幫助我們在查找時跳過一些節點,從而減少查找的時間。
跳表中的節點通常按照升序排列,最底層的節點包含所有元素。每個節點還有一個隨機的層數,用來確定它在哪些層中有指針。一般來說,每個節點的層數都是隨機生成的,但是要滿足一定的概率分布。這樣可以確保跳表的高度不會太高,從而保證其時間復雜度的性能。
在跳表中,查找、插入和刪除操作都是基于每個節點的指針進行的。具體來說,查找操作從較高層開始,按照升序查找節點,如果當前節點的下一個節點的值比要查找的值大,則跳到下一層,繼續查找,直到找到目標節點或者到達最底層。插入和刪除操作也是類似的,只需要在查找到目標節點后,修改其指針即可。
總之,跳表是一種簡單而高效的數據結構,可以在O(log n)的時間復雜度內進行查找、插入和刪除操作。雖然它在實際應用中并不像紅黑樹那樣廣泛使用,但在某些場景下,跳表可以提供比其他數據結構更好的性能表現。