Wann sollte man LinkedList statt ArrayList in Java verwenden?

Question

Ich war schon immer jemand, der einfach nur benutzt:

List<String> names = new ArrayList<>();

Ich verwende die Schnittstelle als Typname für Tragbarkeit damit ich, wenn ich Fragen wie diese stelle, meinen Code überarbeiten kann.

Wann sollte LinkedList verwendet werden über ArrayList und andersherum?

Answer 1

ArrayList ist zufällig zugänglich, während LinkedList ist wirklich billig zu erweitern und Elemente zu entfernen. Für die meisten Fälle, ArrayList ist in Ordnung.

Wenn Sie nicht gerade große Listen erstellt und einen Engpass gemessen haben, werden Sie sich wahrscheinlich nie um den Unterschied kümmern müssen.

Answer 2

In der Regel ziehe ich die eine der anderen vor, je nach der zeitlichen Komplexität der Operationen, die ich mit der jeweiligen Liste durchführen möchte.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|

|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|

Answer 3

Wenn Ihr Code add(0) y remove(0) verwenden Sie eine LinkedList und es ist hübscher addFirst() y removeFirst() Methoden. Andernfalls verwenden Sie ArrayList .

Und natürlich, Guave 's UnveränderlicheListe ist Ihr bester Freund.

Answer 4

Vergleichen wir LinkedList und ArrayList mit den folgenden Parametern:

1. Umsetzung

ArrayList ist die Implementierung der Schnittstelle list für größenveränderliche Arrays, während

LinkedList ist die Implementierung der Listenschnittstelle in Form einer doppelt verketteten Liste.

---

2. Leistung

• get(int index) oder Suchvorgang

  ArrayList Die Operation get(int index) läuft in konstanter Zeit, d. h. O(1), während

  LinkedList Die Laufzeit der Operation get(int index) beträgt O(n) .

  Der Grund dafür ArrayList schneller als LinkedList ist, dass ArrayList ein indexbasiertes System für seine Elemente verwendet, da es intern eine Array-Datenstruktur verwendet,

  LinkedList bietet keinen indexbasierten Zugriff auf seine Elemente, da es entweder vom Anfang oder vom Ende aus (je nachdem, was näher liegt) durchläuft, um den Knoten am angegebenen Elementindex zu finden.

• insert() oder add(Object) Operation

  Einfügungen in LinkedList sind im Allgemeinen schnell im Vergleich zu ArrayList. In LinkedList ist das Hinzufügen oder Einfügen eine O(1) Operation.

  Während in ArrayList Wenn das Array voll ist, d.h. im schlimmsten Fall, fallen zusätzliche Kosten für die Größenänderung des Arrays und das Kopieren von Elementen in das neue Array an, wodurch die Laufzeit der Hinzufügungsoperation in ArrayList O(n) beträgt, andernfalls ist sie O(1).

• remove(int) Vorgang

  Der Löschvorgang in LinkedList ist im Allgemeinen derselbe wie in ArrayList, d.h. O(n).

  Unter LinkedList Es gibt zwei überladene remove-Methoden. Eine ist remove() ohne Parameter, die den Kopf der Liste entfernt und in konstanter Zeit O(1) läuft. Die andere überladene remove-Methode in LinkedList ist remove(int) oder remove(Object), die das als Parameter übergebene Object oder int entfernt. Diese Methode durchläuft die LinkedList, bis sie das Objekt gefunden hat, und löst es aus der ursprünglichen Liste. Daher ist die Laufzeit dieser Methode O(n).

  Während in ArrayList remove(int)-Methode beinhaltet das Kopieren von Elementen aus dem alten Array in das neue, aktualisierte Array, daher ist ihre Laufzeit O(n).

---

3. Umgekehrter Iterator

LinkedList kann in umgekehrter Richtung mit descendingIterator() iteriert werden, während

es gibt keinen descendingIterator() in ArrayList Daher müssen wir unseren eigenen Code schreiben, um die ArrayList in umgekehrter Richtung zu durchlaufen.

---

4. Ursprüngliche Kapazität

Wenn der Konstruktor nicht überladen ist, dann ArrayList erzeugt eine leere Liste mit der Anfangskapazität 10, während

LinkedList konstruiert nur die leere Liste ohne Anfangskapazität.

---

5. Speicher-Overhead

Speicher-Overhead in LinkedList ist im Vergleich zu ArrayList größer, da ein Knoten in LinkedList die Adressen des nächsten und des vorherigen Knotens behalten muss. Während

Unter ArrayList jeder Index enthält nur das eigentliche Objekt (Daten).

---

Quelle

Answer 5

Ich weiß, dass dies ein alter Beitrag ist, aber ich kann ehrlich gesagt nicht glauben, dass das niemand erwähnt hat LinkedList implementiert Deque . Schauen Sie sich nur die Methoden in Deque (und Queue ); wenn Sie einen fairen Vergleich wünschen, versuchen Sie LinkedList gegen ArrayDeque und vergleichen Sie Merkmal für Merkmal.