更快地訪問鏈接列表中的節點

Question

如果列表變大，訪問鏈接列表中的節點會變得非常慢。我確實想到了一種加速訪問的方法：有一個數組（也是LL），每100個節點有一個快捷方式。這樣，如果我想獲得第205個元素，程序將不得不經過這個「路徑」：short cut to [100] -> short cut to [200] -> [201] -> ... -> [205]。這要比整個LL到第205個元素--5個「步長」快得多，而不是204個。是的，如果我想要第n個第99個元素，它會變得更慢，但程序將跳過很大一部分LL在那裏 - 從長遠來看更快。

但是這些捷徑需要在添加和刪除更多元素之後重新調整。刪除不是一個真正的問題 - 刪除一個元素並設置某些快捷方式指向下一個節點 - 這些節點會在正式的第n百個節點處切分。添加更多數據是一個問題 - 添加新元素時，必須將某些節點設置爲指向先前的節點。爲了達到這些要素，該程序必須從最後一個仍然指向第n百分之一的捷徑開始，一路走下列表。除非節點也指向之前的元素，否則整個過程可能會像從一個向量中移除元素一樣慢。

有沒有辦法加快訪問速度，保持相當快地添加和刪除元素的過程？這只是一個好奇的問題，而不是在真實程序中使用它的好主意。

Answer 1

您正在使用錯誤的數據結構。鏈接列表最適用於按順序訪問的列表，而不適用於隨機訪問的集合。爲此，你最好使用某種哈希表。