块状链表（Sqrt Decomposition List 或 Unrolled Linked List）是一种结合数组和链表优势的数据结构。它将数据分成多个块，每个块内部用数组存储，块之间用链表连接。这种结构在插入、删除和区间查询操作上均能达到优秀的均摊复杂度，常用于文本编辑器和动态序列维护。
数据结构原理
- 将序列划分为多个块，每块包含
O(√N)个元素 - 块内用数组存储，支持随机访问
- 块间用链表连接，支持快速插入/删除块
- 维护块大小平衡：过大时分裂，过小时合并
核心操作实现
import java.util.*;
/**
* 块状链表（Sqrt List）
* 结合数组与链表优势，支持高效的插入、删除和区间查询
*/
public class SqrtList {
private static final int DEFAULT_BLOCK_SIZE = 50; // 块大小阈值
/**
* 块节点：包含元素数组和前后指针
*/
static class Block {
List<Integer> data; // 块内数据
Block prev, next; // 前后指针
Block() {
this.data = new ArrayList<>();
}
int size() { return data.size(); }
boolean isFull() { return size() > DEFAULT_BLOCK_SIZE * 2; }
boolean isEmpty() { return size() == 0; }
boolean needMerge() { return size() < DEFAULT_BLOCK_SIZE / 2; }
}
private Block head; // 头节点（哨兵）
private int size; // 总元素数
public SqrtList() {
head = new Block(); // 哨兵节点
size = 0;
}
/**
* 查找第index个元素所在的块及块内偏移
*/
private static class Position {
Block block;
int offset;
Position(Block b, int o) { block = b; offset = o; }
}
private Position find(int index) {
if (index < 0 || index > size) throw new IndexOutOfBoundsException();
Block cur = head.next;
int passed = 0;
while (cur != null) {
if (passed + cur.size() > index) {
return new Position(cur, index - passed);
}
passed += cur.size();
cur = cur.next;
}
// index == size，返回最后一个块的末尾
Block last = head;
while (last.next != null) last = last.next;
return new Position(last, last.size());
}
/**
* 在指定位置插入元素
*/
public void insert(int index, int value) {
if (index == size) {
// 在末尾插入
Block last = head;
while (last.next != null) last = last.next;
if (last == head) {
last = addBlockAfter(head);
}
last.data.add(value);
} else {
Position pos = find(index);
pos.block.data.add(pos.offset, value);
}
size++;
maintain();
}
/**
* 删除指定位置的元素
*/
public int remove(int index) {
Position pos = find(index);
int val = pos.block.data.remove(pos.offset);
size--;
maintain();
return val;
}
/**
* 获取指定位置的元素
*/
public int get(int index) {
Position pos = find(index);
return pos.block.data.get(pos.offset);
}
/**
* 区间查询 [l, r) 的和
*/
public long rangeSum(int l, int r) {
if (l >= r) return 0;
long sum = 0;
Position start = find(l);
Position end = find(r - 1);
if (start.block == end.block) {
// 在同一块内
for (int i = start.offset; i <= end.offset; i++) {
sum += start.block.data.get(i);
}
} else {
// 起始块尾部
for (int i = start.offset; i < start.block.size(); i++) {
sum += start.block.data.get(i);
}
// 中间完整块
Block mid = start.block.next;
while (mid != null && mid != end.block) {
for (int v : mid.data) sum += v;
mid = mid.next;
}
// 结束块头部
for (int i = 0; i <= end.offset; i++) {
sum += end.block.data.get(i);
}
}
return sum;
}
/**
* 维护块大小平衡：分裂过大块，合并过小块
*/
private void maintain() {
Block cur = head.next;
while (cur != null) {
Block next = cur.next;
if (cur.isFull()) {
split(cur);
} else if (cur.needMerge() && cur != head.next) {
mergeWithPrev(cur);
}
cur = next;
}
}
/**
* 将块分裂为两个块
*/
private void split(Block block) {
Block newBlock = new Block();
int mid = block.size() / 2;
for (int i = mid; i < block.size(); i++) {
newBlock.data.add(block.data.get(i));
}
while (block.size() > mid) {
block.data.remove(block.size() - 1);
}
// 插入链表
newBlock.next = block.next;
newBlock.prev = block;
if (block.next != null) block.next.prev = newBlock;
block.next = newBlock;
}
/**
* 与前一节点合并
*/
private void mergeWithPrev(Block block) {
Block prev = block.prev;
if (prev == head) return;
prev.data.addAll(block.data);
prev.next = block.next;
if (block.next != null) block.next.prev = prev;
}
private Block addBlockAfter(Block prev) {
Block block = new Block();
block.prev = prev;
block.next = prev.next;
if (prev.next != null) prev.next.prev = block;
prev.next = block;
return block;
}
public int size() { return size; }
/**
* 打印所有元素
*/
public void printAll() {
Block cur = head.next;
System.out.print("[");
boolean first = true;
while (cur != null) {
for (int v : cur.data) {
if (!first) System.out.print(", ");
System.out.print(v);
first = false;
}
cur = cur.next;
}
System.out.println("]");
}
public static void main(String[] args) {
SqrtList list = new SqrtList();
// 批量插入
for (int i = 1; i <= 20; i++) {
list.insert(list.size(), i * 10);
}
System.out.print("初始序列: ");
list.printAll();
// 插入操作
list.insert(5, 999);
System.out.print("在位置5插入999: ");
list.printAll();
// 删除操作
list.remove(3);
System.out.print("删除位置3: ");
list.printAll();
// 区间求和
System.out.println("区间[2,8)的和: " + list.rangeSum(2, 8));
// 随机访问
System.out.println("位置7的元素: " + list.get(7));
}
}
复杂度分析
- 插入/删除：
O(√N)。定位块O(块数) = O(√N)，块内操作O(块大小) = O(√N)，分裂/合并O(√N)。 - 单点查询：
O(√N)，定位到对应块后随机访问。 - 区间查询：
O(√N + 区间跨度/块大小)，最坏O(√N + K)。 - 空间复杂度：
O(N)，存储所有元素。
应用场景
- 文本编辑器：Rope数据结构的核心思想，支持在任意位置高效插入/删除字符。
- 动态序列维护：需要频繁插入删除但不需要极致查询效率的场景。
- 离线算法预处理：将操作分批处理，每批内部用数组优化。
总结
块状链表通过分块策略平衡了数组的随机访问优势和链表的动态扩展优势。虽然单点操作复杂度 O(√N) 不如平衡树的对数级，但其实现简单、常数小，且天然支持区间批量操作，在特定场景下非常高效。
