java - Javaデータ構造配列リストとリンクリスト

Question

ランダムに生成された数値のリストがあり、それらを構造体に格納してから、生成された順序で構造体から削除したいと考えています。

したがって、最初に削除するのが最適なデータ構造が必要です。

リンク リストと配列リストの両方で O(1) が削除されました

一方が他方よりも優れていますか？もしそうなら、どのような方法で？

Answer 1

Java では、LinkedListクラスがQueueインターフェースを実装します。つまり、キューとして機能します。を使用.add()すると、リストの最後 (キュー) に配置され、 を使用すると.remove()、リスト (キュー) の先頭からプルされます。

an からの取得ArrayListは O(1) ですが、削除はそうではありません。次の点を考慮してください。

ArrayList<Integer> al = new ArrayList<Integer>();
al.add(1);
al.add(2);
al.add(3);

あなたのリストalは{1, 2, 3}です。

次のようにします。al.remove(0)

その後、alです{2, 3}。しかし、これを行うには、リストの先頭を削除すると、先頭の後の他のすべてのオブジェクトを 1 単位下にシフトする必要がありました。つまり、実際には O(n) でした。テールを削除する場合、削除は O(1) のみです。ただし、毎回ヘッドを取り外す必要があります。