2

Java 7のLinkedList APIを調べていたところ、興味深いことに気付きました。「前（または後）を削除する」タイプの方法はないようです。たとえば、100 要素の LinkedList があり、最初の 20 要素を削除したい場合、Java は、開始ポインターを 21 番目の要素に移動して 20 要素間のリンクを削除するのではなく、一度に 1 つずつ削除するように強制するようです。および21.これは、Javaが強制的に行うように見えるため、O(n)時間ではなく、O(1)時間で実行できる操作のようです。

ここで何かが足りないのでしょうか、それとも Java の明らかな穴ですか?

編集

sublist(int, int)List インターフェイスのメソッドを認識しています。これは、一般的な「最初 (または最後) の n を切り取る」ユースケースよりもわずかに効率が悪いと思います。

編集2

n番目の要素を見つけることはO（1）ではないことを指摘したすべての人に触れてください。最初の n-1 個の要素を簡単に切り捨てることができるにもかかわらず、n 番目を見つけるのに O(n) 時間かかります。

ただし、Dilum Ranatunga が指摘するように、指定された位置にイテレータが既に存在する可能性があります。この場合、「私はここにいます。私の前にあるものはすべて取り除いてください」と言うと便利です。

4

6 に答える 6

5

あなたが何をしても、それはまだO（n）操作です。

リンクされたリストの個々のノードに直接アクセスできないため、最初にリストを走査して 21 番目のノードにアクセスする必要があります。そこにいると、リストを「先頭に戻す」には O(1) になりますが、アトミック操作全体ではまだ O(n) です。

于 2012-07-18T17:28:41.180 に答える
1

LinkedList は List インターフェイスから sublist メソッドを継承します。情報はここにありますhttp://docs.oracle.com/javase/6/docs/api/java/util/List.html#subList(int , int)

于 2012-07-18T17:27:16.360 に答える
1

を呼び出して、21 からリストの最後までのサブリストlist = list.subList(21, list.size())を取得できます。

操作は O(1) ですが、元の のラッパー クラスのように機能するLinkedListを取得し、サブリストのオフセットを使用してメソッドを委譲します。AbstractList.SubListLinkedList

これは一定の時間ですが、これは新しいリストではないことに注意してください。リストのサイズが n から m になった場合、リストで呼び出される後続の線形時間メソッドは、O(m) ではなく O(n) で実行されます。

于 2012-07-18T17:28:10.283 に答える
1

前の各ノードには Node.next (チェーン内の次のノード) のアドレスが含まれているため、すぐに N 番目の要素にジャンプすることはできません。したがって、20 個の要素を自然にトラバースする必要があり、O(n) ランタイムが発生します。

例えば：

[ノード 1、ノード 2 のアドレス] -> [ノード 2、ノード 3 のアドレス] -> etc... -> [ノード 20、ノード 21 のアドレス]

「ノード21のアドレス」はノード20に到達しないと取得できず、そのためにはノード19などから「ノード20のアドレス」を取得する必要があります。

于 2012-07-18T17:29:53.743 に答える
1

O(1) 時間でアイテム n を見つけるためのアルゴリズムは何ですか? これは、n 番目の項目を見つけてそれを先頭として設定するための O(n) 操作です。20回の削除と比較して、いくつかの中間ポインター割り当てを節約できますが、大きな利益ではありません.

于 2012-07-18T17:30:14.457 に答える
0

Javajava.util.Listは API を定義しますlistIterator()。ListIterator持っていprevious()ます。

したがって、必要なイディオムは次のとおりです。

// some loop construct {
  listIter.previous();
  listIter.remove();
}
于 2012-07-18T17:30:42.270 に答える