ArrayList: Listen in Arrays speichern

Listen sind eine der wichtigsten Datentypen überhaupt. Zwei unterschiedliche Speicherungsmethoden sind bei Listen gebräuchlich: 1. Listen in Arrays und 2. verkettete Listen. In diesem Video wird die Datenstruktur ArrayList vorgestellt. Wie aber kann man eine ArrayList verlängern, wenn die Kapazität ihres Speicherarrays erschöpft ist. Verdoppelt man in einem solchen Fall die Listenkapazität, so kann man durch eine amortisierte Kostenanalyse zeigen, dass der durchschnittliche Aufwand bei Verlängerung der Liste um ein weiteres Element O(1) ist. 00:00 - Intro 00:19 - Was sind Listen? 03:05 - ArrayList 06:00 - Vergrößerung der Liste über die Kapazität hinaus 07:45 - Pseudocode der Zugriffsmethoden 17:38 - Amortisierte Laufzeitanalyse 28:32 - Zusammenfassung Laufzeiten der Zugriffsmethoden - Verkettete Listen: https://youtu.be/WgYu2FuQ4c0 - Einführung Datenstrukturen: https://youtu.be/fnhbhmEWeoI