ArrayList vs. LinkedList

„Wie wäre es mit ein wenig Gehirnjogging? Ich hoffe, deine grauen Zellen sind noch in Form.“

„In der Tabelle der Container und Collections hast du vor kurzem gesehen, dass dieselbe Schnittstelle mehrere Implementierungen haben kann. Jetzt erkläre ich dir, wozu wir so etwas brauchen. Und wie sich ArrayList von LinkedList unterscheidet.“

„Es ist so, dass Collections auf unterschiedliche Weise implementiert werden können und keine Implementierung in jedem Fall die beste ist. Bei einem Vorgehen sind manche Operationen schnell, aber andere langsam. Für ein anderes Vorgehen gilt möglicherweise das Gegenteil. Es gibt keine perfekte Einheitslösung.“

„Deshalb wurde die Entscheidung getroffen, mehrere Versionen derselben Collection zu implementieren. Jede Implementierung musste für einige eng definierte Einsatzzwecke optimiert werden. So entstanden verschiedene Collections. Nehmen wir zwei Klassen als Beispiele unter die Lupe: ArrayList und LinkedList.“

„Intern ist ArrayList als gewöhnliches Array implementiert. Deshalb erfordert das Einfügen eines Elements in der Mitte, dass wir zuerst alle nachfolgenden Elemente um eins verschieben und dann das neue Element an die freie Position legen. Das Abrufen und Ändern von Elementen (get, set) ist schnell, da diese Operationen einfach das entsprechende Array-Element ansprechen.“

„LinkedList hat eine andere interne Struktur. Es ist als Liste mit miteinander verbundenen Elementen implementiert: eine Zusammenstellung von verschiedenen Elementen, von denen jedes Referenzen auf das nächste und vorherige Element in der Liste speichert. Um ein Element in die Mitte einer solchen Liste einzufügen, muss man nur die Referenzen seiner zukünftigen Nachbarn ändern. Um das Element Nr. 130 abzurufen, müssen wir aber jedes Objekt von 0 bis 130 durchlaufen. Mit anderen Worten, Abruf- und Änderungsoperationen sind langsam. Sieh dir die folgende Tabelle an:“

„Verstehe. Langsam begreife ich es. Gibt es Kriterien oder Regeln dafür, welche Collection in einer bestimmten Situation am besten geeignet ist?“

„Damit es nicht zu kompliziert wird, hier eine einfache Regel: Wenn du häufig Elemente in der Mitte der Collection einfügen (oder entfernen) möchtest, solltest du eine LinkedList verwenden. In allen anderen Fällen funktioniert ArrayList besser.“

„Wir werden uns in späteren Lektionen damit befassen, wie sie aufgebaut sind. Für den Moment geht es uns darum, wie sie eingesetzt werden.“