隨筆檔案

單鏈表的訪問改進

我們知道單鏈表的插入和刪除的時間復雜度是 O(1)
但是其訪問的時間復雜度是 O(N)，不能實現隨機訪問。

而順序表是隨機訪問的，插入和刪除的時間復雜度是 O(N)

針對單鏈表的訪問弊端，如何改進單鏈表數據結構，使得訪問的效率有所提升？

每種數據結構都有各自的優劣以及適用情況。

這里有幾種方案，其實不能算在方案吧，而是采用其他數據結構替換的策略。

第一種方案
采用平衡二叉樹，插入、刪除、訪問的復雜度都是 O(logN)
或者紅黑樹，插入、刪除、訪問的時間復雜度都是 O(logN)
STL 中的 set、map 可以完成該功能。

第二種方案
采用分段的策略
針對每個節點的值，根據值進行分段，段數視具體情況而定。
插入和刪除的時間復雜度保持不變，還是 O(1)
訪問的時間復雜度變為 O(N / 段的數目)
這種方式訪問的時間復雜度得到一定的改進，但是是常數級的。
這種策略實質上是哈希。
哈希函數為除法函數。
例如有 0 1 2 3 4 5 6 7 8 9 十個數，可以分為兩段，0 - 4 為第一段，5 - 9 為第二段。
訪問一個數時，首先計算其所在的段，m / 5，得到所在段的首地址，然后去遍歷訪問。

第三種方案
采用線索二叉樹
線索二叉樹將二叉樹線索化，二叉樹可以想鏈表那樣操作。插入和刪除的時間復雜度都是 O(1)。
訪問按照二叉樹的方式，這時二叉樹是平衡二叉樹，訪問的時間復雜度是 O(logN)。

幾種方案的比較
                插入和刪除   訪問
單鏈表              O(1)    O(N)
平衡二叉樹    O(logN)    O(logN)
分段                 O(1)    O(N / 段的數目)
線索二叉樹         O(1)    O(logN)

總結
這幾種方案，與其說是改進，不如說是更換另一種數據結構。

另外哈希方式，最好在存在大量數據的情況下使用，否則會浪費空間，因為哈希表很大。

針對單鏈表訪問效率的改進，另一個角度是采用輔助性數據結構，記錄一些信息，以方便快速地訪問。