4

両端で挿入を処理できる必要があるデータ構造を必要とするパブリック メソッドを実装しています。O(N)時間ArrayList.add(0,key)かかるので、代わりに a を使用することにしました -とメソッドは両方ともO(1)時間かかるはずです。LinkedListaddaddFirst

ただし、既存の API を使用するには、私のメソッドはArrayList. だから私は2つのアプローチがあります：

(1) useを使用して、 N/2が前に追加され、N/2が最後に追加されるN要素LinkedListのすべての追加を行います。次に、コンストラクター を呼び出して、これを次のように変換します。LinkedListArrayListArrayListreturn new ArrayList<key>(myLinkedList);

(2) and を使用してN/2要素を後ろに追加しArrayList、 callを使用してN/2要素を前に追加します。これを返します。ArrayList.add(key)ArrayList.add(0,key)ArrayList

時間の複雑さの点でどのオプションがより最適化されているかについて、誰かコメントできますか? Java がコンストラクターをどのように実装しているかはわかりませんArrayList。これは、どのオプションが優れているかを決定する重要な要素です。

ありがとう。

4

2 に答える 2

1

最初のメソッドは、リスト全体を反復します。

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html#ArrayList(java.util.Collection)

コレクションの反復子によって返される順序で、指定されたコレクションの要素を含むリストを構築します。

iteratorこれは、インターフェースを使用していると合理的に推測できます。

2 番目の方法は、前に要素を追加するたびに要素をシフトします (そして、時々サイズを変更します)。

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html#add(int , E)

このリストの指定された位置に、指定された要素を挿入します。現在その位置にある要素 (存在する場合) と後続の要素を右にシフトします (インデックスに 1 を追加します)。

関数に関する公式の仮定を考えると、最初の方法がより効率的です。

参考: を使用すると、より多くのマイレージを獲得できますLinkedList.toArray

于 2013-08-01T03:49:59.703 に答える