![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
| p | 検索時に幅をたどる回数(平均) | 1ノードあたりの追加容量(平均) |
| 1/2 | 1x16=16 | 14バイト |
| 1/4 | 3x8=24 | 7.7バイト |
| 1/8 | 1+7x5=36 | 5.7バイト |
| 1/16 | 15x4=60 | 4.8バイト |
| 1要素あたりの追加容量 | 挿入 | 削除 | 検索 | i番目の要素を得る | 一つ先の要素を得る | 一つ前の要素を得る | この要素は何番目か | キーなしでも並べられるか | |
| 川合版 Indexable skiplist (KISL) | 7.7バイト | O(logN) | O(logN) | O(logN) | O(logN) | O(1) | O(logN) | O(logN) | yes |
| 平衡二分木 | 8.0バイト以上 | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | O(logN) | たぶんyes |
| B-tree | 8.0バイト以上 | O(logN) | O(logN) | O(logN) | O(logN) | ほぼO(1) | ほぼO(1) | O(logN) | たぶんyes |
| 双方向リスト | 8.0バイト | O(1) | O(1) | O(N) | O(N) | O(1) | O(1) | O(N) | yes |
| 片方向リスト | 4.0バイト | O(N) | O(N) | O(N) | O(N) | O(1) | O(N) | O(N) | yes |
| ポインタ配列 | 4.0バイト | O(N) | O(N) | O(logN) | O(1) | O(1) | O(1) | O(1) or O(N) | yes |
| コメント | お名前 | NameLink | |
