ArrayListまたはLinkedListから要素を削除する方が効率的ですか?
-
10-07-2019 - |
質問
理論上、 ArrayList
または LinkedList
から要素を削除する方が効率的ですか?
解決
「簡単」です(つまり、より効率的です) LinkedList
からそれらを削除するには、 ArrayList
から削除するには、後続のすべての要素をリスト内の新しい位置に移動する必要があるため、配列の要素には新しい値を割り当てる必要があります。リンクリストでは、1つのポインター(または2つ、二重リンクリストの場合)のみを再割り当てする必要があります。
他のヒント
まあ、(二重リンク)リストからの要素の削除はO(1)です。ただし、配列から削除するには、残りの要素を配列内の1つのスペース(O(n))にシフトする必要があります。
とは言っても、インデックスでリストの特定の要素を取得するのはO(n)であり、インデックスで配列の特定の要素を取得するのはO(1)です。
したがって、実際の削除では、LinkedListの方が優れています。配列とLinkedListの詳細については、こちらをご覧ください。
所属していません StackOverflow