一、概述
有時候我們需要設計這樣一種資料結構：它能快速在要求位置插入或者删除一段資料。先考慮兩種簡單的資料結構：數組和連結清單。數組的優點是能夠在O(1)的時間内找到所要執行操作的位置，但其缺點是無論是插入或删除都要移動之後的所有資料，複雜度是O(n)的。連結清單優點是能夠在O(1)的時間内插入和删除一段資料，但缺點是在尋找操作位置時，卻要周遊整個連結清單，複雜度同樣時O(n)的。這兩種資料結構各有優缺點，我們可以把數組和連結清單的優點結合來，這就構成了一個新的資料結構：塊狀連結清單，結合數組和連結清單的優缺點的塊狀連結清單其各種操作的時間複雜度均為O(sqrt(n))。
二、塊狀連結清單的各種操作
塊狀連結清單是結合了數組和連結清單的優缺點，塊狀連結清單本身是一個連結清單，但是連結清單儲存的并不是一般的資料，而是由這些資料組成的順序表。每一個塊狀連結清單的節點，也就是順序表，可以被叫做一個塊。塊狀連結清單通過使用可變的順序表的長度和特殊的插入、删除方式，可以在達到的複雜度。塊狀連結清單另一個特點是相對于普通連結清單來說節省記憶體，因為不用儲存指向每一個資料節點的指針。
1、定位操作
定位操作其實可以當作是查找，我們當然是先要定位到元素所在的節點，然後在該節點裡面的數組裡面尋找我們要的節點；
2、分裂節點
将某個節點分裂成兩個節點；
3、插入操作
首先定位要插入的位置，然後将所在節點分裂成兩個節點，并将資料放到第一個節點的末尾。 如果要插入的是一大塊資料，首先要将資料切成多個塊其中、每個塊對應一個塊狀連結清單的一個節點，并将這些塊鍊起來，然後将它們插入那兩個節點之間。插入的操作圖類似下面：
4、删除操作
首先定位删除元素的位置，然後按照數組删除元素的方法删除該資料。如果删除一大塊資料，首先要定位資料塊首元素和末元素所在的位置，然後分别将它們所在的節點分裂成兩個節點，最後删除首元素和末元素之間的節點即可。
三、關鍵技術
從總體上來看，維護一個連結清單，連結清單中的每個單元中包含一段數組，以及這個數組中的資料個數。每個連結清單中的資料連起來就是整個資料。設連結清單長度為a，每個單元中的數組長度是b。無論是插入或删除，在尋址時要周遊整個連結清單，複雜度是O(a)；對于插入操作，直接在連結清單中加入一個新單元，複雜度是O(1)；對于删除操作，會涉及多個連續的單元，如果一個單元中的所有資料均要删除，直接删除這個單元，複雜度是O(1)，如果隻删除部分資料，則要移動數組中的資料，複雜度是O(b)。總的複雜度是O(a+b)。因為ab=n，取a=b=√n，則總的複雜度是O(√n)。
問題是如何維護a和b大緻等于√n？
在執行插入操作後，如果目前單元中的資料個數>2√n，則将目前單元分割成兩個新單元，每個單元中的資料個數保持為2√n。在執行删除操作後，如果目前單元和目前單元的下一個單元的資料個數和<√n，則将兩個單元合并成一個新單元。執行上述維護操作需要移動數組中的資料，複雜度是O(b)，對于單元的分割和合并均是O(1)的，總的複雜度是O(b)的。這樣，維護操作并不會使總複雜度增加。最終得到一個複雜度是O(√n)的資料結構。
四、應用
1、文本編輯器：http://download.noi.cn/T/noi/noi2003A.pdf
另一種實作：http://www.byvoid.com/blog/noi-2003-editor/