块状链表 Block List

把链表分块、每块上限 √n：任意位置插入/删除/访问降到 O(√n)。观察元素插入后块如何从中点分裂。

速度:

插入序列:

每个块容量上限 S=3；琥珀块=当前操作块，琥珀格子=刚插入元素；块超容量会从中点分裂

空链表

初始化空块状链表（块容量上限 S=3）

步骤 1 / 15初始化

当前高亮行: 1(初始化)

1const S = 3; // 块容量上限（实际取 ⌈√n⌉）

2function insert(v) { // 追加到尾部

3 const [bi, off] = locate(length);

4 blocks[bi].items.splice(off, 0, v);

5 if (blocks[bi].items.length > S)

6 splitBlock(bi); // 超过容量则从中点分裂

加载中…