Java-Linkedlist langsamer als Arraylist beim Hinzufügen von Elementen?

Ja, das stimmt. LinkedList muss bei jeder Einfügung eine Speicherzuweisung vornehmen, während ArrayList weniger davon tun darf, und zwar amortisierte O (1) -Einfügung . Speicherzuweisung sieht billig aus, kann aber tatsächlich sehr teuer sein.

Die lineare Suchzeit ist wahrscheinlich in LinkedList aufgrund der Fundstelle der Referenz langsamer: Die ArrayList -Elemente liegen näher beieinander, also gibt es weniger Cache vermisst .

Wenn Sie vorhaben, nur am Ende von List einzufügen, ist ArrayList die Implementierung der Wahl.

Denken Sie daran:

• Es gibt einen Unterschied in der "rohen" Leistung für eine bestimmte Anzahl von Elementen und in wie unterschiedlichen Strukturen skalieren ;
• verschiedene Strukturen funktionieren bei verschiedenen Operationen unterschiedlich, und das ist im Wesentlichen ein Teil dessen, was Sie bei der Auswahl der zu verwendenden Struktur berücksichtigen müssen.

So hat zum Beispiel eine verknüpfte Liste mehr zu tun, um zum Ende zu addieren, weil sie ein zusätzliches Objekt hat, das hinzugefügt und initialisiert wird, aber was auch immer diese "intrinsischen" Kosten pro Element haben, beide Strukturen haben O (1) Leistung zum Hinzufügen zum Ende der Liste, dh eine effektiv "konstante" Zeit pro Zusatz unabhängig von der Größe der Liste hat, aber diese Konstante wird sich zwischen ArrayList und LinkedList unterscheiden und wahrscheinlich größer sein für Letzteres.

Andererseits hat eine verkettete Liste eine konstante Zeit zum Hinzufügen zum Anfang der Liste, während im Fall einer ArrayListe die Elemente entlang "shuftied" werden müssen, eine Operation, die eine gewisse Zeit proportional zur Anzahl benötigt von Elementen. Aber für eine gegebene Listengröße, sagen wir, 100 Elemente, kann es immer noch schneller sein, 100 Elemente zu "shuften", als ein einzelnes Platzhalterobjekt der verknüpften Liste zuzuweisen und zu initialisieren (aber zu der Zeit, zu der du kommst tausend oder eine Million Objekte oder was auch immer der Schwellenwert ist, wird es nicht sein).

Bei Ihren Tests sollten Sie wahrscheinlich sowohl die "rohe" Zeit der Operationen bei einer gegebenen Größe als auch die Art und Weise betrachten, in der diese Operationen skalieren , wenn die Listengröße zunimmt.

Warum glaubst du, dass LinkedList schneller wäre? Im allgemeinen Fall ist ein Einfügen in eine Array-Liste einfach ein Fall des Aktualisierens des Zeigers für eine einzelne Array-Zelle (mit O (1) wahlfreiem Zugriff). Die LinkedList-Einfügung ist auch wahlfreier Zugriff, muss jedoch ein "Zellen" -Objekt zuweisen, um den Eintrag zu speichern, und ein Zeigerpaar aktualisieren, sowie schließlich den Verweis auf das einzufügende Objekt festlegen.

Natürlich muss das Array der ArrayList in regelmäßigen Abständen geändert werden (was nicht der Fall ist, wenn es mit einer ausreichend großen Anfangskapazität ausgewählt wurde), aber da das Array exponentiell wächst, sind die amortisierten Kosten niedrig und ist begrenzt durch O(lg n) complexity.

Einfach gesagt - Inserts in Array-Listen sind viel einfacher und daher insgesamt viel schneller.

In diesen Fällen kann die verknüpfte Liste aus mehreren Gründen langsamer als die Array-Liste sein. Wenn Sie am Ende der Liste einfügen, ist es wahrscheinlich, dass die Array-Liste diesen Speicherplatz bereits zugewiesen hat. Das zugrundeliegende Array wird normalerweise in großen Blöcken erhöht, da dies ein sehr zeitaufwendiger Prozess ist. In den meisten Fällen erfordert das Hinzufügen eines Elements auf der Rückseite nur das Beibehalten einer Referenz, während die verknüpfte Liste die Erstellung eines Knotens erfordert. Das Hinzufügen von Vorder- und Mitte sollte für beide Listentypen eine unterschiedliche Leistung bringen.

Das lineare Überstreichen der Liste ist in einer Array-basierten Liste immer schneller, da das Array nur normal durchquert werden muss. Dies erfordert eine Dereferenzierungsoperation pro Zelle. In der verknüpften Liste müssen die Knoten der Liste auch dereferenziert werden, wobei die doppelte Zeit benötigt wird.

Wenn ein Element zur Rückseite einer LinkedList hinzugefügt wird (in Java ist LinkedList tatsächlich eine doppelt verknüpfte Liste), handelt es sich um eine O(1) -Operation, wie das Hinzufügen eines Elements an die Front. Das Hinzufügen eines Elements zur Position i th ist ungefähr% O(i) operation.

Wenn Sie also an den Anfang der Liste setzen, wäre eine LinkedList wesentlich schneller.

ArrayList ist schneller beim Zugriff auf zufällige Indexdaten, aber langsamer beim Einfügen von Elementen in der Mitte der Liste, da Sie mithilfe der verknüpften Liste nur die Referenzwerte ändern müssen. Aber in einer Array-Liste müssen Sie alle Elemente nach dem eingefügten Index kopieren, einen Index dahinter.

EDIT: Gibt es keine Linkedlist-Implementierung, die das letzte Element berücksichtigt? Auf diese Weise würde das Einfügen am Ende mithilfe der verketteten Liste beschleunigt.