怎樣改造一個有序的鏈表,使其能夠具有高效找到Node在鏈表中index(在鏈表中的第幾個結點)?

比如說,我現在有一個有序的鏈表list(存在刪除,插入), 通過map&能夠馬上找到結點的地址,希望立即知道Node在鏈表中的index(從頭開始,在鏈表中的第幾個結點),例如,list有20個node,根據key查找到當前的node,在list的第五個結點。該怎麼改造這個鏈表呢?

struct Node
{
int key
...........
}


這個東西的名字叫random-access list。一個有序的序列,能夠按下標快速找到元素,同時又能像鏈表一樣支持快速的拼接。一般來說random access能做到O(log n)的時間。有很多數據結構能做到這一點。

Bootstrapping one-sided flexible arrays

可以在側重拼接性能和側重random access之間均衡。

Finger Trees: A Simple General-purpose Data Structure

這個是最容易實現的。

polymatheia - Improving RRB-Tree Performance through Transience

這個是目前最先進的,兼顧了緩存友好性。


Order-statistic tree


SkipList 稍微增加一些變數.

有時間補充一種實現.


用線索樹來當鏈表,插入O(lgn),刪除O(lgn),查找O(lgn),從一個節點遍歷到下一個節點O(1)。

話說這還是我剛畢業進微軟的時候的面試題。


簡單啊,你讓插入刪除變成O(N)就好了。。。


AVL樹每個節點記錄左右子樹分別有幾個節點就行了吧。這樣你要的int IndexOf(T item)和T Get(int index)還有添加刪除都是O(log(N))。


用跳錶。題主可以搜一下。舉個例子。鏈表1,2,3,4,5,6。1還指向3,3指向5。最開始一次跳2步,比較大小,如果節點在後面,繼續跳。否則一次跳1步。可以根據情況設置多層的。。


可以使用跳錶,實現例子參見redis 跳躍表的實現


splay


參見《演算法導論》序統計樹


你還是發原始問題,這樣大家就不用給你的歪路上面出主意了。


用splay吧


推薦閱讀:

計算機圖形學研究生在研究生階段怎麼提升自己實力?
有哪些 C++ 的 JSON 庫比較好呢?
C++為什麼函數參數個數不同還能出錯啊?
依賴C++的情況下該如何選擇做GUI界面的框架?
C語言和C++ C#的區別在什麼地方?

TAG:程序員 | 演算法 | C | 數據結構 | CC |