Einfügen in der Mitte von LinkedList in Java

Question

Stellen Sie sich vor, Sie haben eine LinkedList einfügen Elemente {A, B, C, D, E, F}, diese Operation sind O (1) jetzt möchte ich zurück zum Anfang gehen und addiere {G, H, I}, so dass die endgültige LinkedList wie folgt aussehen würde: {G, H, I, A, B, C, D, E, F}.

Ich kann dies tun list.add(index, content) verwenden, aber diese erheblich ineffizient ist, da jede Operation O (N) sein würde. Später würde ich gerne weiter am Schwanz hinzufügen. Ich bin sicher, es gibt eine Möglichkeit, all diese Operationen in O (1) Zeit, ohne meine eigene verknüpfte Liste, ich weiß einfach nicht wie.

Edit: Also, was ich wirklich wissen wollen, ob Java eine Art Iterator/Zeiger hat, i, wobei ein von dort in O (1), beispielsweise i = 3 {A, B, C einsetzen kann,^D, E, F}, Einfügen {G}, {H}, {I} würde die Liste wie {A, B, C, G, H, I, D, E, F} aussehen lassen. list.addAll funktioniert, aber ich muss zuerst eine Liste erstellen. Wie auch immer, wenn eine solche Methode existiert, möchte ich nicht weitermachen, ohne sie zu kennen.

Schließlich stelle ich diese Frage, um diesen Uva Richter zu lösen problem Ich weiß, wie es zu lösen, aber wenn andere Szenarien nicht verallgemeinert werden kann, lerne ich nichts.

Answer 1

Nach dem Javadoc:

doppelt verketteten Liste Umsetzung der Liste und Deque-Schnittstellen.

Alle Operationen funktionieren wie erwartet für eine doppelt verkettete Liste. Operationen, die in der Liste indexieren, durchqueren die Liste vom Anfang oder vom Ende, je nachdem, was näher am angegebenen Index liegt.

In Bezug auf Ihr Anliegen:

ich diese (Index, Inhalt) mit list.add tun könnte, dies ist jedoch erheblich ineffizient, da jede Operation O (N) sein würde. Später würde ich gerne weiter am Schwanz hinzufügen.

Dies ist nicht wahr. Das Einfügen von Elementen am Anfang oder am Ende der Liste ist so gestaltet, dass sie O (1) Laufzeit hat. Daher gibt es nichts, worüber man sich Sorgen machen müsste.

---

Bearbeiten: Nach dem Lesen der UVa Problembeschreibung, meine Antwort oben steht immer noch. Außerdem möchte ich hinzufügen, dass ein guter Weg, um das Problem zu lösen, darin besteht, ganze Textzeichen gleichzeitig hinzuzufügen, und nicht ein Zeichen gleichzeitig. Alle Zeichen zwischen zwei Home/Ende-Tasten drücken sollten als eine einzige unzerbrechliche Zeichenfolge behandelt werden. Dann fügen wir diese Strings am Anfang oder Ende einer LinkedList<String>, nicht LinkedList<Character>. Es gibt immer noch keine Notwendigkeit, sich um das Einfügen in der Mitte zu kümmern, noch ist es notwendig, einen imaginären Einfügungsiterator zu haben.