隨筆檔案

單鏈表的訪問改進(jìn)

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

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

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

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

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

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

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

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

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

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

另外哈希方式，最好在存在大量數(shù)據(jù)的情況下使用，否則會(huì)浪費(fèi)空間，因?yàn)楣１砗艽蟆?/p>

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