Bei der Verwendung von Sammlungen, in welchen Fällen ist die Durchlaufzeit schneller: in ArrayList oder in LinkedList?

Die Iteration von Elementen in den Collections ArrayList und LinkedList in Java unterscheidet sich in der Leistung aufgrund ihrer internen Struktur.

• ArrayList basiert auf einem Array, daher erfolgt der Zugriff auf ein Element per Index in O(1). Die Iteration mit einer for-Schleife mit Indizes ist sehr schnell.
• LinkedList ist eine doppelt verkettete Liste, bei der der Zugriff auf ein Element per Index das Durchlaufen der Liste vom Anfang oder Ende erfordert, was O(n) Zeit in Anspruch nimmt.

Daher ist das Durchlaufen aller Elemente mit einem Iterator oder einer foreach-Schleife für beide Sammlungen ungefähr gleich, aber wenn die Iteration mit Indizes erfolgt (z.B. get(i) in einer Schleife), ist ArrayList deutlich schneller.

Beispiel:

ArrayList<String> arrayList = new ArrayList<>();
LinkedList<String> linkedList = new LinkedList<>();
// Listen füllen

// Schnelles Durchlaufen in ArrayList
for (int i = 0; i < arrayList.size(); i++) {
    String item = arrayList.get(i); // O(1)
}

// Langsames Durchlaufen in LinkedList bei Verwendung von Indizes
for (int i = 0; i < linkedList.size(); i++) {
    String item = linkedList.get(i); // O(n)
}

// Es wird empfohlen, Iterator oder foreach für LinkedList zu verwenden
for (String item : linkedList) {
    // Element verarbeiten
}

Daher ist die Iteration in ArrayList schneller, insbesondere wenn der Zugriff per Index erforderlich ist.