はじめに
前回の記事では動的配列とリストについて解説をしました。
しかしまだ動的配列に関しては詳しく説明していないので、
この記事では、動的配列がどのようなアイデアで作られているかを説明します。
動的配列のアイデア
動的配列は、静的配列をつかってリストを実装したもの。
リストの長さ（size, length）以上の配列を保持する。
この時の配列長を特にcapacityなどと言う。
配列の末尾の方は使わずに無駄に確保している時もありますが、
配列長を気にしなくてもいいリストのメリットが得られます。
リストに要素が挿入されて配列長を超えてしまった場合は、
今より大きな配列を再確保してそちらに要素をコピーします。
新しい配列の長さは言語によって異なりますが、
古い配列の長さの1.5倍や2倍とすることが多いです。
List<Int> arrayList = new ArrayList<>(); arrayList.add(1); arrayList.add(2); arrayList.add(3);
arrayList ┣━ size(int) : 3 ┣━ _array(int[]) : [1, 2, 3, 0] ┗━ _capacity(int) : 4
想定される操作の実装と最悪時間計算量
参照（ get(i) ）
参照は静的配列の参照をそのまま利用します。
そのため最悪時間計算量は O(1) となります。
挿入と削除（ insert(e, i), delete(i) ）
挿入や削除を行う際は、配列の要素を詰めるため O(n) かかります。
arrayList: (size=3, _array=[1, 2, 3, 0]) ↓ ↓ insert(e=4, i=0) ↓ arrayList: (size=4, _array=[4, 1, 2, 3]) ↓ ↓ delete(i=0) ↓ arrayList: (size=3, _array=[1, 2, 3, 0])
末尾の要素の挿入や削除の場合は、詰める処理が必要ないため、
特別に O(1) で操作を完了することができます。
| リストの想定される操作 | 時間計算量 |
|---|---|
参照 get(i) |
O(1) |
挿入 insert(e, i) |
O(n) （末尾の要素は O(1) ） |
削除 delete(i) |
O(n) （末尾の要素は O(1) ） |
最後に
この記事では動的配列の紹介をしました。
動的配列のアイデアと、計算量などの性質が分かったのではないでしょうか。
さて、実はリストを実装したデータ構造には連結リストもあります。
次の記事では連結リストを紹介して比較します。
