ギャップバッファ

草案．



参照（検索）コストと，メモリコストを両立する為のバッファ．
主にデータが小さいときに有効．

予めバッファ内に，ギャップ（空白）を持っておき，挿入削除の際にこれを上手く活用する．


■単純なバッファ

配列：探索，挿入削除に時間がかかる．拡張が出来ない（出来るがメモリに悪い）

リンクリスト：リンクのためのポインタが必要．データが小さい場合，ポインタによってデータサイズが膨らむ



■ギャップバッファ

ある一定のサイズの配列を１単位としたノードで構成される．
その中にギャップ（空白）を持ち，空白の先頭と終端位置を記憶しておく．

データ挿入の際には，挿入位置までギャップをずらすという工程が入る．

挿入するノードにギャップなかった場合には，新規ノードを作成し，リンクリストとして繋ぐ．
その際，そのノードの挿入位置以降の要素を全て新規ノードに移動することで，既存ノードのギャップを新たに確保する．






書きかけ