介紹

有時(shí)候我們需要設(shè)計(jì)這樣一種數(shù)據(jù)結(jié)構(gòu)：它能快速在要求位置插入或者刪除一段數(shù)據(jù)。先考慮兩種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表。數(shù)組的優(yōu)點(diǎn)是能夠在O(1)的時(shí)間內(nèi)找到所要執(zhí)行操作的位置，但其缺點(diǎn)是無(wú)論是插入或刪除都要移動(dòng)之后的所有數(shù)據(jù)，復(fù)雜度是O(n)的。鏈表優(yōu)點(diǎn)是能夠在O(1)的時(shí)間內(nèi)插入和刪除一段數(shù)據(jù)，但缺點(diǎn)是在尋找操作位置時(shí)，卻要遍歷整個(gè)鏈表，復(fù)雜度同樣時(shí)O(n)的。這兩種數(shù)據(jù)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，我們可以把數(shù)組和鏈表的優(yōu)點(diǎn)結(jié)合來(lái)，這就構(gòu)成了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)：塊狀鏈表，結(jié)合數(shù)組和鏈表的優(yōu)缺點(diǎn)的塊狀鏈表其各種操作的時(shí)間復(fù)雜度均為O(sqrt(n))。
從總體上來(lái)看，維護(hù)一個(gè)鏈表，鏈表中的每個(gè)單元中包含一段數(shù)組，以及這個(gè)數(shù)組中的數(shù)據(jù)個(gè)數(shù)。每個(gè)鏈表中的數(shù)據(jù)連起來(lái)就是整個(gè)數(shù)據(jù)。設(shè)鏈表長(zhǎng)度為a，每個(gè)單元中的數(shù)組長(zhǎng)度是b。無(wú)論是插入或刪除，在尋址時(shí)要遍歷整個(gè)鏈表，復(fù)雜度是O(a)； 對(duì)于插入和刪除操作，需要移動(dòng)數(shù)組的元素，所以總的復(fù)雜度是O(a+b)。因?yàn)閍b=n，取a=b=√n，則總的復(fù)雜度是O(√n)。
問(wèn)題是如何維護(hù)a和b大致等于√n？
在執(zhí)行插入操作后，如果當(dāng)前單元中的數(shù)據(jù)個(gè)數(shù)>2√n，則將當(dāng)前單元分割成兩個(gè)新單元，每個(gè)單元中的數(shù)據(jù)個(gè)數(shù)保持為√n。在執(zhí)行刪除操作后，如果當(dāng)前單元和當(dāng)前單元的下一個(gè)單元的數(shù)據(jù)個(gè)數(shù)和<√n，則將兩個(gè)單元合并成一個(gè)新單元。執(zhí)行上述維護(hù)操作需要移動(dòng)數(shù)組中的數(shù)據(jù)，復(fù)雜度是O(b)，對(duì)于單元的分割和合并均是O(1)的，總的復(fù)雜度是O(b)的。這樣，維護(hù)操作并不會(huì)使總復(fù)雜度增加。最終得到一個(gè)復(fù)雜度是O(√n)的數(shù)據(jù)結(jié)構(gòu)。

在STL中，deque內(nèi)部就是使用塊狀鏈表保證在首尾能夠快速插入。并能夠以索引的方式查找元素。