Unterschied zwischen ArrayList und LinkedList in Java

Sowohl ArrayList als auch LinkedList implementieren die List-Schnittstelle, aber was ist dann der Unterschied? Der Hauptunterschied zwischen ArrayList und LinkedList liegt in ArrayList, das mit einem erweiterbaren Array implementiert wird. Wenn der ArrayList weitere Elemente hinzugefügt werden, nimmt ihre Größe dynamisch zu. Auf seine Elemente kann direkt mit den Methoden get() und set() zugegriffen werden, da ArrayList im Wesentlichen ein Array ist.

LinkedList als verknüpfte Liste implementiert ist, sind diese Add- und Remove-Leistungen besser als die von ArrayList, aber sie sind schlecht für die Methoden get() und set().

In diesem Artikel werden wir uns einige Unterschiede zwischen LinkedList und ArrayList ansehen und versuchen zu verstehen, wann und wo LinkedList anstelle von ArrayList verwendet werden sollte.

ArrayList vs. LinkedList

Alle Unterschiede zwischen LinkedList und ArrayList haben eine Quelle, die der Unterschied zwischen einem Array und einer LinkedList (verknüpfte Liste) ist.

1) Da die Die Suche in ArrayList basiert auf dem Index des Elements und ist daher sehr schnell. Die Methode get(index) hat eine Komplexität von O(1), aber das Entfernen ist teuer, da Sie alle Elemente versetzen müssen. Im Fall von LinkedList hat es keinen direkten Zugriff auf die Elemente, Sie müssen die gesamte Liste durchgehen, um ein Element abzurufen, seine Komplexität ist gleich O(n).

2) Einfügungen sind in LinkedList im Vergleich zu ArrayList einfach, da beim Ändern der Größe und beim Hinzufügen des Elements zu LinkedList kein Risiko besteht und seine Komplexität gleich O(1) ist. während ArrayList im schlimmsten Fall alle Elemente mit einer Komplexität von O(n) verschiebt.

3) Das Löschen ist wie das Einfügen, besser in LikedList als in ArrayList.

4) LinkedList hat mehr Speicher als ArrayList, da in ArrayList jeder Index mit dem aktuellen Objekt verknüpft ist, aber im Fall von LinkedList ist jeder Knoten mit dem Element und der Adresse des nächsten und vorherigen Knotens verknüpft.

Wann sollten LinkedList und ArraList in Java verwendet werden

Offensichtlich ist LinkedList nicht so beliebt wie ArrayList, aber in einigen Fällen immer noch eine gute Wahl:

1) Ihre Anwendung benötigt keinen wahlfreien Zugriff, Da dieser Vorgang in diesem Fall darin besteht, die gesamte Liste durchzugehen.

2) Ihre Anwendung verfügt über mehr Einfügen und Entfernen als Wiederherstellung. Beide Vorgänge sind in LikedList.

Verwenden Sie ArrayList in Java in diesen Situationen, wenn Sie nicht synchronisierten Zugriff benötigen. ArrayList ist schnell und einfach zu bedienen.

Beispiel für ArrayList

ArrayList< String> al = new ArrayList< String> (); 
al.add("a"); 
al.add("c"); 
al.add("e"); 
al.add("z"); 
al.add("t"); 
al.add("m"); 

for(String s: e){
 System.out.println(e); 
}

Beispiel für LinkedList

LinkedList< Ganzzahl> llist = neue LinkedList< Ganzzahl> (); 
llist.add(8); 
llist.add(9); 
llist.add(5); 
llist.add(2); 
llist.add(6); 
 
Iterator< Ganzzahl> it = llist.iterator(); 
while(it.hasNext()){
 System.out.println(it.next()); 
}

Performance von ArrayList und LinkedList

Die Zeitkomplexität beider Listen:

Operation	ArrayList	LinkedList
get()	O(1)	O(n)
add()	O(1)	O(1)
remove()	O(n)	O(1)

- ArrayList hat eine Zeitkompatibilität von O(n) sowohl für die add()- als auch für die remove()-Operation, aber O(1) für die Operation am Ende der Liste oder für das Abrufen eines Elements mit der get()-Methode.

- LinkedList hat eine Komplexität von O(n) für die get()-Operation, aber O(n) für die remove-Operation remove().

Dieser Code testet die Leistung basierend auf der Zeit, die für die Ausführung einer Reihe von Operationen benötigt wird:

import java.util.ArrayList; 
import java.util.LinkedList; 

public class ArrayListVsLinkedList {

 public static void main(String[] args) {
 ArrayList< Ganzzahl> alist = neue ArrayList< Ganzzahl> (); 
 LinkedList< Ganzzahl> llist = neue LinkedList< Ganzzahl> (); 
 
 /******************************/
 /* Die add()-Methode */
 /******************************/
 
 // ArrayList
 long tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 999999; i++) {
 alist.add(i); 
 }
 long tpsfin = System.currentTimeMillis(); 
 lange Dauer = tpsfin - tpsdebut; 
 System.out.println("ArrayList add: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 999999; i++) {
 llist.add(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 Dauer = tpsfin - tpsdebut; 
 System.out.println("LinkedList add: " + duration); 
 
 /******************************/
 /* Die get()-Methode */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 99999; i++) {
 alist.get(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 Dauer = tpsfin - tpsdebut; 
 System.out.println("ArrayList get: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 0; i <= 99999; i++) {
 llist.get(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 Dauer = tpsfin - tpsdebut; 
 System.out.println("LinkedList get: " + duration); 
 
 /******************************/
 /* Die remove()-Methode */
 /******************************/
 // ArrayList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 9999; i >=0; i--) {
 alist.remove(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 Dauer = tpsfin - tpsdebut; 
 System.out.println("ArrayList remove: " + duration); 
 
 // LinkedList
 tpsdebut = System.currentTimeMillis(); 
 
 for (int i = 9999; i >=0; i--) {
 llist.remove(i); 
 }
 tpsfin = System.currentTimeMillis(); 
 Dauer = tpsfin - tpsdebut; 
 System.out.println("LinkedList remove: " + duration); 
 }
}

Ergebnis:

ArrayList add: 398
LinkedList add: 987
ArrayList get: 180
LinkedList get: 43276
ArrayList remove: 8721
LinkedList remove:  233

Leistung und Unterschied ArrayList vs. LinkedList

Der Hauptunterschied liegt in den Methoden get() und remove(). Es ist klar, dass LinkedList beim Abrufen von Daten sehr zeitaufwändig ist, da es jedes Mal, wenn es auf ein Element zugreifen möchte, die gesamte Liste durchläuft. ArrayList hat direkten Zugriff. Im Gegensatz dazu verbraucht ArrayList viel Zeit für die remove().