はじめに
Javaにおける競技プログラミングのメモです
計算量
List
ArrayListとLinkedListの使い分けについて
get()
ArrayListはランダムアクセスには強い。
- ArrayList O(1)
- LinkedList O(n)
add(element)
末尾に要素を追加するメソッド。
ArrayListは新たにArrayが生成されてしまうケースにおいてO(n)となるが、それ以外のケースではO(1)。どのような場合にArrayの生成が発生するかは記述が見当たらなかった。
- ArrayList O(1)->O(n)
- LinkedList O(1)
add(index, element)
任意の場所に要素を追加する場合。LinkedListもインデックスにたどり着くまでにループを回す必要があるため、O(n)である点に注意したい。
- ArrayList O(n)
- LinkedList O(n)
remove(element)
リストは、要素を検索する必要があるためO(n)です。
- ArrayList O(n)
- LinkedList O(n)
remove(index)
LinkedListはgetと同じようにランダムアクセスにO(n)ですが、ArrayListもO(n)です。削除そのものはO(1)であるものの、削除後にシフトが必要となるためです。
- ArrayList O(n)
- LinkedList O(n)
ただ、シフトよりもループのほうがコストが低いため、LinkeListの方が好ましい。
参考
下記のページを参考にしました。
- https://www.baeldung.com/java-collections-complexity
- https://javatutorial.net/difference-between-arraylist-and-linkedlist-in-java
- https://dzone.com/articles/performance-analysis-of-arraylist-and-linkedlist-i
記事情報
- 投稿日：2021年8月19日
- 最終更新日：2021年8月19日