hinzufügen Element in einem Arraylist effizient zu einem bestimmten Index in Java

Question

Ich brauche ein Element vom Typ Person (meine eigene definierte Klasse) in einem Arraylist am Index einfügen i

Ich weiß, ich add(int index, E element) verwenden kann.

Aber gibt es eine effiziente Methode, um dies zu tun, wie in meiner Liste dauert es etwa 1,5 ms im Durchschnitt (Daten gesammelt über 1000 Insertion und dann Durchschnitt).

Answer 1

Diese Einfügung findet in O (n) statt, weil sie alle Elemente nach unten verschieben muss und im Worst-Case-Szenario wird jedes Element nach unten verschoben. (Korrigiertes Java sagt, es ist O (n), weil sie eine mathematische Formel verwenden)

Wenn Sie eine schnelle Einfügung wünschen, fügen Sie sie entweder am Ende der Arraylist hinzu oder verwenden Sie eine Hashmap, die eine konstante Zeit ist.

in hashmap einfügen: HashMap peopleMap = new HashMap .....

peopleMap.put (person.name, Person); // (oder was auch immer Sie verfolgen möchten)

Dies legt den Schlüssel für den Namen der Person und den Wert für die Person fest.

Sie können auch eine HASHAMP mit Schlüssel versuchen (je nachdem, was Sie verfolgen möchten) und den Index für die Person in einem Halter-Array bewerten. Die Einfügung ist O (i), Nachschlagen O (i) und Sie können es auch sortieren (Ich überlasse es als eine Übung dem Leser)

Wenn der ganze Zweck davon ist zu sortieren, dann der Einfachheit halber Sie könnten in eine priorityQueue (nLogn) einfügen und dann alles in das Array einfügen, was Ihnen ein sortiertes Array liefert.

Answer 2

Wenn Ihre Aufgabe mehr Insertion/Deletion intensiv ist, können Sie immer java.util.LinkedList verwenden.

• ArrayList hat eine begrenzte Größe. Jedes Mal, wenn Sie ein Element hinzufügen, stellt Java sicher, dass es passt - so dass es die ArrayList vergrößert. Wenn die ArrayList schneller wächst, wird viel Array-Kopieren stattfinden.
• LinkedList fügt das Element einfach an die richtige Stelle (Verknüpfen der Knoten herum), ohne die gesamte ArrayList zu vergrößern und zu kopieren.
• Nachteile der LinkedList sind, wenn Sie nach einem Element suchen. Da es keine Indizes hat, muss es vom Anfang bis zum Ende der Liste durchlaufen werden, um ein Element zu finden.

Für LinkedList:

• get ist O (n)
• hinzuzufügen, ist O (1)
• entfernen, ist O (n)
• Iterator.entfernen O (1)

Für ArrayList:

• get ist O (1)
• add ist O (1) abgeschrieben, sondern O (n) ungünstigsten Fall, da das Array muss Größe verändert werden und kopiert
• entfernen ist O (n)

Answer 3

Wenn Sie add

arryListInstance.add(positionIndex, Object); 

012 mit

Das Objekt wird nach dem Sichten der vorhandenen Objekte um 1 Position hinzugefügt. Daher wird der durchschnittliche Fall dieser Operation O (n).

Während einfache hinzufügen

arryListInstance.add(positionIndex, Object); 

am Ende des arrayListInstance das Objekt erstellt. Im besten Fall ist dieser Vorgang O (1), aber im schlimmsten Fall wird es O (n), wenn die maximale Kapazität erreicht ist: wie eine neue ArrayList-Instanz intern erstellt wird und alle Inhalte dort kopiert werden.

Sie stehen vor dieser Frage, weil einer der beiden Gründe, von denen der 1. vermieden werden kann:

1. Sie nicht genügend Anfangskapazität für Ihre Arraylist-Objekt definiert haben. Daher muss vor jeder arrayListInstance.add (position, Objekt) einen neuer arrayListInstance wird mit erhöhter Kapazität erstellt und dann den vorhandenen Elemente aus der ursprünglichen Liste kopiert werden und dann schließlich hinzufügen durchgeführt wird. Dies kann vermieden werden, wenn Sie genau wissen, wie viele Daten Sie mit dieser Liste bearbeiten möchten, und die Anfangskapazität entsprechend definieren (ebenso wie die Anzahl der möglichen Elemente). Wenn Sie die Anfangskapazität nicht vorhersagen können, ist es besser, die Daten in Chargen zu verarbeiten.
2. Nach jedem Einfügen an einer beliebigen Stelle außer dem letzten verursacht Sichten von bestehenden Elementen. Dies ist unvermeidlich. arrayListInstance.add (positionIndex, Objekt) wird in O (n) Zeit ausgeführt, wenn positionIndex nicht der letzte Index der ArrayList ist. Selbst wenn Sie LinkedList verwenden, können Sie keine konstante Zeit hinzufügen Operation erreichen, die ein Element in die Liste an einem anderen Index als nach dem letzten Element hinzufügt.