2013-08-27 9 views
8

私は自分のコードに2つのLinkedListを持っています。私はこのリストがもう必要なくなり、必要なすべてのデータを持つ新しいリストだけが必要になります。我々はを作成した場合、我々は正常に行うように私が何かを探しています2つのリンクされたリストをコピーせずにまとめる - Java、標準APIを使用

...すべてたびに、

を私は.addAll()を使用することができますが、パフォーマンスは私の巨大な問題であると私はコピーするのを待つカント、参照を追加しますリンクリストを作成し、最後のノードを1つ目から2番目のノードに接続します。java apiからLinkedListクラスを使用してリンクを作成する方法はありますか?操作は私の問題はちょうど、ちょうど通常、私が必要なものを行うことができますlinkedlists、のパフォーマンスに関してれ、ほぼ同じ意味がコレクションのマージ


は、別のケースです。また、「合併」はあいまいな言葉のようなものですが、私が望むのは、どのような順序であっても、パフォーマンスを心に留めておくだけです。合併が可能かどうかはわかりません...

別のこと私の質問はちょうどAPIに関するもので、私は自分のコード(上司の要件)を構築するのではないので、これとは違うのです:Javaで一定時間に2つのリストをマージする - 有用な答えではありません..

答えて

3

LinkedListを使用している場合は、インデックス付きアクセスが遅いため、インデックス付きアクセスに興味がない可能性があります。ただし、リストには参照のみが格納されるため、挿入/削除の少ない非常に大きなリストArrayListでヒープ上の各ノードを割り当てる必要がないため、メモリ効率が向上します)

List契約のほとんどを提供するものですそれ。

これはよくそのような場合には、あなたは非常に簡単に生活をしている...あなたが望むすべてはあなたにIterable<String>を与えるものだということが考えられます。

public class UberIterable<T> implements Iterable<T> { 
    private final List<List<T>> lists; 
    public UberIterable(List<T>... lists) { 
    this.lists = Arrays.asList(lists); 
    } 
    public Iterator<T> iterator() { 
    return new Iterator<T>() { 
     Iterator<List<T>> metaNext = lists.iterator(); 
     Iterator<T> next; 
     public boolean hasNext() { 
     while (true) { 
      if (next != null && next.hasNext()) return true; 
      if (metaNext.hasNext()) next = metaNext.next(); else return false; 
     } 
     } 
     public T next() { 
     if (!hasNext()) throw new NoSuchElementException(); 
     return next.next(); 
     } 
     public void remove() { 
     throw new UnsupportedOperation(); 
     } 
    } 
    } 
} 

あなたを与える基本的な実装であること多くのリストのマージされたビューListの契約をもっともっとしたいのであれば、ListIteratorのよりよい実装でのみ同じトリックを繰り返すことができます。おそらく多くのことが起こります。最後にAbstractListを拡張し、新しいメソッドListIteratorでオーバーライドします実装

+0

@ phlogratosは私が鉱山を入力している間に答えました。あなたが依存関係としてGuavaを使用できるのであれば、してください... Guavaはあなたや私が書くことができるよりもはるかに正確でよくテストされた実装を持っています...私の答えはGuavaのフードの下で起こっていることを示していますコード –

+0

この解決策は今までのところ最も実用的なものと思われます。私はグアバを使うことができると思いますが、すでにたくさんのコーディングがあります。 リンクリストは挿入と削除が主な操作であるため正確に使用しています;) – Victor

1

これを行う方法の1つは、getLast()を使用してリストの最後の要素を取り除き、addFirst()を正面に追加することです。

しかしながら、addAll()は何もコピーしておらず、容易に使用することができます。

LinkedListのノードオブジェクトの実際のインスタンス化に問題がある場合は、独自のバージョンを実装して、そのAPIの実装メカニズムの多くを公開する必要があります。

+2

しかし、それは新しいエントリを割り当て、すべての*参照をコピーします。 OPは(合理的に)1つの参照のみをコピーしたい。 – pamphlet

+1

'getLast()' + 'addFirst()'はリストをマージしません。 – arshajii

+2

あなたはそうです。新しいノードを作成する際のオーバーヘッドが問題になる場合、私はそれを解決する唯一の方法はカスタム実装を作成することだと思います。 JavaのLinkedList実装では、ノードをクライアントコードに公開していないため、「マージ」するメカニズムはありません。 – Surveon

2

これを行う唯一の方法は反射を使用することです... When you take a look at the source code of LinkedList、サブクラスEntry<E>がプライベートであることがわかります。最初と最後のエントリを他に接続したい場合は問題ですリストをマージするために、

更新:(あなたがチェックを追加しない限り)愚かな私見であるJDK 7、であるためOracle changed the name of the subclass Entry to Node and changed the order of arguments of the constructor!でも反射が、安全ではありません。

ダーティーソリューション:ソースコードをコピーしてprivateのキーワードをpublicに変更してください。しかし、私はこれがOracleによって許可されているかどうかはわかりません。ライセンスを確認してください。

2

私は答えがノーだと思います。 LinkedListによって使用される内部Entryクラスはプライベートであり、LinkedListによって公開されるすべてのパブリックメソッドは一般的なコレクションで機能します。

あなたのユースケースは当然ですが、この実装はそれをサポートしていません。

0

import java.util。LinkedList;

パブリッククラスMergeLinkedList {

public static void main(String[] args) { 

    LinkedList<String> mainlist = new LinkedList<String>() ; 

    mainlist.add("A"); 
    mainlist.add("B"); 

    LinkedList<String> secondlist = new LinkedList<String>() ; 

    secondlist.add("C"); 
    secondlist.add("D"); 

    mainlist.addAll(secondlist); 
    System.out.println(mainlist); 
} 

}

O/P [A、B、C、D]

あなたが)(のaddAllを使用しなければなりません。

1

リストを実装ラッパー/プロキシクラスを作成していない理由2つのサブリストへの参照が含まれている場合は、Listメソッド(または、少なくとも下流に必要なもの)を実装してください。作業は少しですが、いずれかのリストをコピーするのが実際に問題があるように思えます。

+0

phlogratosは自分のタイプを入力しているときに彼のコメントを掲載しました。 – Jay

関連する問題