2つの大きなコレクションを1つにマージする必要があります。どのコレクションタイプを使用できますか？私は個々の要素にランダムアクセスする必要はありません。私はリンクリストに行くつもりだが、Javaで2つのリンクされたリストをO（1）のランタイムでマージすることはできない。これは新しいリストに各要素をコピーする必要があるので。JavaマージO（1）の2つのコレクション
編集：すべてのあなたの答えをありがとう。あなたの答えは非常に役立ち、私は仕事を終わらせることができました。次回は、リンクされたリストの独自の実装を使用して始めます。
あなたはGuavaのIterables.concatのいずれかの方法を使用して、（1）Oに連結Iterableビューを作成することができます
Iterable<T> combined = Iterables.concat(list1, list2);
これは、あなたがコピーすることなく、1つのオブジェクトとして両方のリストのすべての要素を反復することができます任意の要素。
理論上、O（1）に2つのリンクリストをマージすることができます。最初のノードの最後のノードを2番目のノードの最初のノードに向けるだけです。
addAllコレクションメソッドは、イテレータについて話しているので、O（n）の実行時間を意味するようです。詳細はJVM固有のものかもしれません...
O（n）で結合するコレクションはありません。あなた自身をロールバックしなければならないかもしれません。
私はこの問題をJavaでどうやって解決するのかという疑問があると思います。したがって、彼は自分のクラスを作成せずに、他のコレクションと同様に最終結果を扱うことができます。 +1質問のbtw –
私はそれを知っているが、Janが言ったように、私はこれがJava自体で既に可能かどうかを知りたい。 – Tiddo
最後の仮定は実際にJavaで保持されますか？ –
ここで最も簡単な解決策は、リストのリストです。単純なラッパー関数が必要だが、何も複雑でないことを意味する。
私はあなたの最善の策は、List>を引数としてとり、委譲するListの実装を作成することです。言い換えれば、リストのリストを持っていて、それらを1つのリストとして振る舞います。リスト1の要素を過ぎると、リスト2を見ることになります。
何らかの理由で、私はグアバがそのようなリストを持っていると考えました。しかし、私はjavadocsでそれを見つけることができません。
であり、標準のListインタフェースを実装しているため、他のコード全体で使用できます。 +1 –
リンクリストをマージするのは確かにO（1）なので、配列ベースのリストは同じ方法、つまり複数のObject []をリンクしていると考えることができます。
上記の実装がありますが、middle/startから削除/挿入すると、ArrayListよりも高速です。 繰り返しは事実上同じです。ランダムアクセスは少し遅くなる可能性があります。
私はCompositeCollectionクラスをapache.commonsから提案したいと考えましたが、source codeを見ると、これもO（n）で実行されます。要素を反復処理するだけで、ColinDの示唆に基づいてGoogle Collectionsを使用したくない場合は、独自の複合イテレータを簡単に作成できます。
public class CompositeCollectionIterator<T> implements Iterator<T>{
private Iterator<T>[] iterators;
private int currentIteratorIndex = 0;
public CompositeCollectionIterator(Collection<T>... aCollections) {
iterators = new Iterator[ aCollections.length];
for (int i = 0, aCollectionsLength = aCollections.length; i < aCollectionsLength; i++) {
Collection<T> collection = aCollections[ i ];
iterators[i] = collection.iterator();
}
}
public boolean hasNext() {
if (iterators[currentIteratorIndex].hasNext()) return true;
else if (currentIteratorIndex < iterators.length - 1){
currentIteratorIndex++;
return hasNext();
}
return false;
}
public T next() {
return iterators[currentIteratorIndex].next();
}
public void remove() {
iterators[currentIteratorIndex].remove();
}
}
あなたはがちょうどオブジェクトのコレクションを持っており、O（1）時間でそれらをマージしたい、と独自のデータ構造を実装する気にしない場合は、これを行うための最も簡単な方法は、使用することですアンバランスなバイナリツリー：各ノードはリーフ（値を格納する）または2つのツリーの組み合わせのいずれかであり、抽象スーパークラスまたはインタフェースを持つ2つのクラスとして実装できます。深さ優先のトラバーサルを使用して要素を抽出することができます。
これは、基本的にColinDのイテレーター連結の提案と同じですが、もっと裸の骨です。
キャッチは、このコレクションを反復処理する
はO（nは
）ではないということです！
n +
m）ここで、
mは、実行したマージの数です（1つは通過するノードなので）。これは私のソリューションとColinDの両方に当てはまります。私は、この問題に対するすべての可能な解決法が真であるかどうかはわかりません。
上記のことは気にしないでください。この方式の下では、すべてのマージ、少なくとも一つの要素を追加するので、メートル < Nので、反復コストは依然としてO（N）です。 （あなたはイテレータの連結を使用する場合は、あなたが頻繁にコストを追加すると、空のイテレータを連結していないことを確認してください。）の最初のと最後の要素へのポインタをあなたのコレクションとして2つのリンクされたリストを使用して、保存することにより
それぞれのリスト（両方のポインタは潜在的にアイテムの追加/削除時に更新する必要があります）では、両方のリストをO（1）でマージできます - 最初のリストの最後の要素を2番目のリストの最初の要素に接続し、それに応じて最初/最後のポインタ。
LinkedListの基本ノードに直接アクセスすることはできないため、Javaでリンクリストを独自に実装する必要があります。最初のリストは2番目のリストの最初の要素になります。
幸いなことに、データ構造のコースでは非常に一般的なトピックなので、リンクリストの実装をJavaで簡単に見つけることができます。たとえば、hereは1つです。名前はスペイン語ですが、ListaEncadenada（ "LinkedList"）とNodoLista（ "ListNode"）のコードは非常に単純で、自明である必要があります。リストの最初と最後の要素へのポインタであり、必要に応じて簡単に変更できます。
ソート済みリストの遅延マージはどのようにして発音しますか？マージされた結果はO（1）に組み込むことができ、実際に評価されるまで、償却されたO（1）をリスト上のすべての演算に追加します。 –
あなた自身LinkedListを実装することはできますが、LinkedListはそれ自体で大きな時間を費やします。 – bestsss
'Javaで2つのリンクされたリストをO（1）'のランタイムでマージすることはできません。 Javaで独自のリンクリストを実装する場合は、Javaでリンクされた2つのリストをO（1）の実行時にマージできます。このステートメントは、標準ライブラリの実装でのみ当てはまります。したがって、ステートメントには「2つのjava.util.LinkedListをO（1）のランタイムでマージすることはできません。 –