怎樣改造一個有序的鏈表,使其能夠具有高效找到Node在鏈表中index(在鏈表中的第幾個結點)?
01-04
比如說,我現在有一個有序的鏈表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#的區別在什麼地方?