- 記事一覧/
Java の ArrayDequeクラス 各種操作の計算量
Java
ArrayDeque
データ構造
計算量
⚠️
目次
JavaのArrayDequeクラスの各種操作の計算量をまとめました。 参考情報は、JDK 21の API Specificationです。
ArrayDeque クラス #
- 参照元: ArrayDeque
まとめ #
| 操作 | 速度 | 計算量 | 備考 |
|---|---|---|---|
| 追加 | ◎ | 定数時間 | 先頭または末尾に対してのみ可能 |
| 取得 | ◎ | 定数時間 | 先頭または末尾に対してのみ可能 |
| 削除（先頭・末尾） | ◎ | 定数時間 | |
| 削除（途中） | △ | 線形時間 | remove, removeFirstOccurrence,removeLastOccurrence, iterator.remove |
| 検索 | △ | 線形時間 | contains |
| 一括操作 | △ | 線形時間 | addAll, removeAll, retainAll など |
※
iterator.removeは、イテレーターのremoveメソッドを指しています。 また、線形時間は償却定数時間も含みます。
ほとんどの操作が定数時間で処理されます。
contains と 中間要素の削除 が線形時間になることだけ、覚えておけば良さそうです。
メソッド一覧 #
定数時間 #
O(1) で処理される 定数時間 または 償却定数時間 のメソッドは、以下の通りです。
- add
- addFirst
- addLast
- clear
- element
- getFirst
- getLast
- isEmpty
- offer
- offerFirst
- offerLast
- peek
- peekFirst
- peekLast
- poll
- pollFirst
- pollLast
- pop
- push
- removeFirst
- removeLast
- size
線形時間 #
O(n) で処理される 線形時間 のメソッドは、以下の通りです。
- remove
- removeFirstOccurrence
- removeLastOccurrence
- contains
- iterator.remove
- 一括操作（bulk operation）
おわり