怎樣改造一個有序的鏈表，使其能夠具有高效找到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吧