java - 中央値アルゴリズムの中央値を実装するには、ArrayList と Linkedlist のどちらが適していますか?

Question

Javaで中央値アルゴリズムの中央値を実装しようとしています。これら 2 つのリストの実装のうち、リストのトラバーサルと比較のコストが低いのはどちらでしょうか? ありがとう！

Answer 1

の場合は O(1)、 の場合はO(n) を取るデータ構造へのランダム アクセスがアルゴリズムで必要になるため、 an のArrayList方が若干効率的です。ArrayListLinkedList

LinkedListLinkedListは、削除操作 ( の場合は O(1)および の場合は O(n) ) の方が効率的ですArrayListが、アルゴリズムではそうではありません。