Ich arbeite an einem Stück Code, das ziemlich heiß ist, und ich muss Elemente von einem LinkedList ( l1 ) zu einem anderen LinkedList ( l2 ) hinzufügen.
Es ist nicht möglich, addAll(Collection) method zu verwenden, da Iterator verwendet wird, um über die gesamte Collection zu iterieren.
Es scheint mir, dass es möglich sein sollte, einfach die letzte Node von l1 so zu setzen, dass sie auf die erste Node von l2 zeigt. Aber ich konnte dafür keine geeignete Methode finden? Benötige ich meine eigene LinkedList Implementierung, um das zu bekommen?
Laut den Kommentaren besteht das Ziel darin, etwas wie eine "Ansicht" auf der verketteten Liste zu erstellen - was bedeutet, dass die Daten nicht kopiert werden sollten. Stattdessen sollten die angegebenen Listen wie eine einzelne Liste erscheinen.
Eine Möglichkeit, wie dies implementiert werden könnte, ist das Erweitern von AbstractList . Die Implementierung von get(int) und size() ist ziemlich trivial. Der entscheidende Punkt ist, ein Iterator für die verkettete Liste zu erstellen. Das Folgende ist eine sehr einfache Skizze, wie dies erreicht werden könnte (aber siehe die Hinweise unten)
Vom Konzept her wäre es sinnvoller, von AbstractSequentialList zu übernehmen: Das AbstractList bietet Stub-Implementierungen, z.B. von iterator() , das schließlich an get(int) delegiert, während AbstractSequentialList die "entgegengesetzten" Stub-Implementierungen anbietet, z. von get(int) , die schließlich an iterator() delegiert. Dies erfordert jedoch eine ListIterator<T> -Implementierung, die ein wenig fummeliger ist als die oben erwähnte triviale Skizze.
Beachten Sie auch, dass ich davon ausgegangen bin, dass die resultierende Ansicht nicht änderbar sein sollte - dies sollte jedoch mit der angegebenen Beschreibung übereinstimmen.
Und schließlich, beachten Sie, dass es (natürlich) bereits Implementierungen für diese und ähnliche Aufgaben gibt, und diese Implementierungen möglicherweise weit ausgeklügelter sind als die oben skizzierten. Zum Beispiel bietet Google Guava verschiedene Iterators#concat Methoden, mit denen Sie mehrere Iteratoren verketten können. Wenn Sie also bereits Guava verwenden, könnte die Implementierung der oben genannten iterator() -Methode auf
Es scheint, als ob die erforderliche Funktion von der Standardbibliothek nicht unterstützt wird. Sie können jedoch die Reflektion verwenden, um eine konstante Zeit beim Zusammenführen verknüpfter Listen zu erreichen. Ich habe den folgenden Code nicht richtig getestet, nur um zu zeigen, wie er erreicht werden kann:
%Vor%}
Nein. Sie können nicht zwei java.util.LinkedList s hinzufügen, um ein weiteres in der konstanten Zeit O (1) auszugeben.
Im Prinzip können Sie tatsächlich zwei Linked-List-Datenstrukturen in konstanter Zeit O (1) hinzufügen, aber sie müssen auf die richtige Weise implementiert werden. Wie Sie erwähnen, sollte die Implementierung die beiden Listen kombinieren, indem sie den Knoten des letzten mit dem Knoten des ersten verbindet und nicht über beide Listen iteriert.
Tags und Links java collections linked-list