隨筆檔案

單鏈表的訪問改進

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

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

針對單鏈表的訪問弊端，如何改進單鏈表數(shù)據(jù)結(jié)構(gòu)，使得訪問的效率有所提升？

每種數(shù)據(jù)結(jié)構(gòu)都有各自的優(yōu)劣以及適用情況。

這里有幾種方案，其實不能算在方案吧，而是采用其他數(shù)據(jù)結(jié)構(gòu)替換的策略。

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

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

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

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

總結(jié)
這幾種方案，與其說是改進，不如說是更換另一種數(shù)據(jù)結(jié)構(gòu)。

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

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