Java, LinkedList und ArrayList

von Hubert Schmid vom 2013-04-07

In Java werden zwei Implementierungen der Schnittstelle java.util.List häufig verwendet: java.util.LinkedList und java.util.ArrayList. Erstere zeichnet sich durch das schnelle Einfügen und Löschen an beliebigen, zuvor bestimmten Positionen aus, wohingegen Letztere den schnellen, wahlfreien Zugriff unterstützt. Dieser Unterschied sollte jedem Entwickler in der Ausbildung vermittelt worden sein. Doch welche Implementierung ist besser geeignet, wenn nur Operationen verwendet werden, deren Laufzeiten sich im Ο‑Kalkül nicht unterscheiden?

Ich komme auf diese Frage, weil ich kürzlich beim Durchschauen eines fremden Quelltexts wiederholt über Code der folgenden Form gestolpert bin. Die Gemeinsamkeit bestand insbesondere darin, dass an der Datenstruktur List<Thing> nur die Methoden add und toArray aufgerufen wurden, für die sich die Implementierungen LinkedList und ArrayList in ihrem amortisierten, asymptotischen Laufzeitverhalten nicht unterscheiden.

private List<Entity> entities; public Thing[] getThingsWithProperty(Property property) { List<Thing> result = new LinkedList<>(); for (Entity entity : entities) { if (match(entity, property)) { result.add(entity.getThing()); } } return result.toArray(new Thing[result.size()]); }

Die Operationen beider Datenstrukturen sind zwar im Ο‑Kalkül identisch – die Laufzeiten der beiden Implementierungen unterscheiden sich hingegen signifikant. In den meisten Fällen sind die Operationen auf einer ArrayList schlicht doppelt so schnell wie auf einer LinkedList, was im Wesentlichen auf zwei Punkte zurückzuführen ist:

Aus diesen Gründen sollte man in Java die ArrayList stets der LinkedList vorziehen – zumindest solange man keine Operationen verwendet, bei denen sich die asymptotischen Laufzeiten unterscheiden. Im obigen Code sollte also die folgende Zeile verwendet werden:

List<Thing> result = new ArrayList<>();

Mit Premature Optimization hat das übrigens nicht zu tun. Denn diese Optimierung wirkt sich weder auf die Software-Architektur noch auf die Korrektheit, Lesbarkeit oder Wartbarkeit des Quelltexts aus. Die Optimierung ist vielmehr unter dem Stichwort Clean Code einzuordnen, wobei übelriechender Code ersetzt und geeignete Datenstrukturen verwendet werden. Die Regel heißt ArrayList und die Ausnahme LinkedList.