介紹
有時候我們需要設(shè)計這樣一種數(shù)據(jù)結(jié)構(gòu)：它能快速在要求位置插入或者刪除一段數(shù)據(jù)。先考慮兩種簡單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表高氮。數(shù)組的優(yōu)點(diǎn)是能夠在O(1)的時間內(nèi)找到所要執(zhí)行操作的位置，但其缺點(diǎn)是無論是插入或刪除都要移動之后的所有數(shù)據(jù)，復(fù)雜度是O(n)的。鏈表優(yōu)點(diǎn)是能夠在O(1)的時間內(nèi)插入和刪除一段數(shù)據(jù)嚎货，但缺點(diǎn)是在尋找操作位置時，卻要遍歷整個鏈表蔫浆，復(fù)雜度同樣時O(n)的殖属。這兩種數(shù)據(jù)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，我們可以把數(shù)組和鏈表的優(yōu)點(diǎn)結(jié)合來瓦盛，這就構(gòu)成了一個新的數(shù)據(jù)結(jié)構(gòu)：塊狀鏈表洗显，結(jié)合數(shù)組和鏈表的優(yōu)缺點(diǎn)的塊狀鏈表其各種操作的時間復(fù)雜度均為O(sqrt(n))。
從總體上來看原环，維護(hù)一個鏈表挠唆，鏈表中的每個單元中包含一段數(shù)組，以及這個數(shù)組中的數(shù)據(jù)個數(shù)嘱吗。每個鏈表中的數(shù)據(jù)連起來就是整個數(shù)據(jù)玄组。設(shè)鏈表長度為a，每個單元中的數(shù)組長度是b谒麦。無論是插入或刪除俄讹，在尋址時要遍歷整個鏈表，復(fù)雜度是O(a)绕德； 對于插入和刪除操作患膛，需要移動數(shù)組的元素，所以總的復(fù)雜度是O(a+b)耻蛇。因為ab=n踪蹬，取a=b=√n胞此，則總的復(fù)雜度是O(√n)。
問題是如何維護(hù)a和b大致等于√n跃捣？
在執(zhí)行插入操作后漱牵，如果當(dāng)前單元中的數(shù)據(jù)個數(shù)>2√n，則將當(dāng)前單元分割成兩個新單元枝缔，每個單元中的數(shù)據(jù)個數(shù)保持為√n布疙。在執(zhí)行刪除操作后，如果當(dāng)前單元和當(dāng)前單元的下一個單元的數(shù)據(jù)個數(shù)和<√n，則將兩個單元合并成一個新單元众弓。執(zhí)行上述維護(hù)操作需要移動數(shù)組中的數(shù)據(jù)详羡，復(fù)雜度是O(b)，對于單元的分割和合并均是O(1)的碴开，總的復(fù)雜度是O(b)的。這樣，維護(hù)操作并不會使總復(fù)雜度增加发钝。最終得到一個復(fù)雜度是O(√n)的數(shù)據(jù)結(jié)構(gòu)。
在STL中波闹，deque內(nèi)部就是使用塊狀鏈表保證在首尾能夠快速插入酝豪。并能夠以索引的方式查找元素。
