前言

块状链表是介于链表和数组之间的数据结构，能够在$O(\sqrt{n})$时间内完成插入、删除、访问操作。

数据结构如图所示。假设最大容量为$n$, 则它有一个长度为$s=\sqrt{n}$的链表。链表中每个结点是一个长度为$2\times \sqrt{n}$的数组。

参考：https://oi-wiki.org/ds/block-list/

实现时，有两个细节需要注意：

• 初始时，只有一个链表结点。随着数据越来越多，当某个结点内数组装满后，将分裂成两个结点。

• 删除数据后，如果数据所在结点为空，则需要删除结点（链表首元结点不用删除）。

本文以BigString为例进行实现。

实现

使用golang实现如下字符串功能：

• Append(str) 向字符串尾部添加一个字符串
• Size() 获取字符串长度
• Insert(index, char) 向字符串某个位置插入一个字符
• Erase(index) 删除某个位置的字符
• At(index) 获了某个位置的字符
• Set(index, char) 设置某个位置的字符

package mainimport ("fmt""math"
)type _Node struct {next *_Nodesize intdata []rune
}type BigString struct {head    *_Node // 没有哨兵，直接就是首元结点size    int    // 字符串大小bukSize int    // 分组大小maxSize int    // 最大字符大小
}func NewBigString(maxLen int) *BigString {if maxLen < 10 {maxLen = 10}// 计算分段长度s := int(math.Sqrt(float64(maxLen)))return &BigString{head:    &_Node{nil, 0, make([]rune, 2*s)},size:    0,bukSize: s,maxSize: maxLen,}
}func (this *BigString) String() string {var str stringfor node := this.head; node != nil; node = node.next {for i := 0; i < node.size; i++ {str += string(node.data[i])}}return str
}/*
*
在尾部插入字符
*/
func (this *BigString) Append(chars string) {for _, char := range chars {this.Insert(this.size, rune(char))}
}/*
*
在尾部插入字符
*/
func (this *BigString) Size() int {return this.size
}/*
*
在指定位置插入字符
*/
func (this *BigString) Insert(index int, char rune) {if this.size < this.maxSize && index >= 0 && index <= this.size {pos := -1for node := this.head; node != nil; node = node.next {if index <= node.size+pos+1 {insertPos := index - pos - 1 // 0 1 2 3 4 | 5 6 7   , index = 6,for j := node.size; j > insertPos; j-- {node.data[j] = node.data[j-1]}node.data[insertPos] = charnode.size++// 结点分裂开if node.size == len(node.data) {node2 := &_Node{node.next, this.bukSize, make([]rune, 2*this.bukSize)}for j := 0; j < this.bukSize; j++ {node2.data[j] = node.data[j+this.bukSize]}node.size -= this.bukSizenode.next = node2}break}pos += node.size}this.size++}
}/*
*
删除指定位置字符
*/
func (this *BigString) Erase(index int) {if index >= 0 && index < this.size {pos := -1var pre *_Node = nilfor node := this.head; node != nil; node = node.next {if index <= node.size+pos {deletePos := index - pos - 1for j := deletePos + 1; j < node.size; j++ {node.data[j-1] = node.data[j]}node.size--// 清理空结点if node.size == 0 {if node != this.head {pre.next = pre.next.next}}break}pos += node.sizepre = node}this.size--}
}/*
*
获取指定位置字符
*/
func (this *BigString) At(index int) rune {if index >= 0 && index < this.size {pos := -1for node := this.head; node != nil; node = node.next {if index <= node.size+pos {atPos := index - pos - 1return node.data[atPos]}pos += node.size}}return 0
}/*
*
设置指定位置字符
*/
func (this *BigString) Set(index int, char rune) {if index >= 0 && index < this.size {pos := -1for node := this.head; node != nil; node = node.next {if index <= node.size+pos {atPos := index - pos - 1node.data[atPos] = charbreak}pos += node.size}}
}

测试

测试结果与测试代码如下。结果表明实现是正确的。

str := NewBigString(225)// 测试 Append, Insert, Stringfmt.Println("【测试 Append, Insert, String】")str.Append("hello world! my name is cloudea. this is my first big string implementation!\n")str.Append("世界 你好! 我的我名字是克劳迪亚。这是我的第一个大字符串实现哦!\n")fmt.Println(str)str.Insert(0, '*')str.Insert(78, '#')fmt.Println(str)for i := 0; i < 40; i++ {str.Insert(100, '$')}fmt.Println(str)// 测试Erasefmt.Println("【测试 Erase】")for i := 0; i < 40; i++ {str.Erase(100)}fmt.Println(str)// 测试测试At 和 Setfmt.Println("【测试At 和 Set】")str.Set(99, '你')str.Set(100, '呀')str.Set(101, 'd')str.Set(102, '二')str.Set(103, '个')for i := 0; i < str.Size(); i++ {fmt.Print(string(str.At(i)))}fmt.Println()