Gap Buffer

テキストエディタのバッファ向けのデータ構造でリストと配列の利点を併せ持つ

配列をベースとして、値を挿入した直後のメモリ領域を空けておく

利点

局所的な要素の挿入と削除がO(1)

要素にインデックスでアクセス可能

リストよりも省メモリ

欠点

ランダムな要素の挿入と削除はO(N)

参考

テキストエディタ向けのデータ構造で Rope、PieceTable というのもあるらしい