In diesem Kapitel werden wir effiziente Datenstrukturen kennenlernen, die auf Basis von Arrays definiert werden. Zunächst werden wir uns mit Hash-Maps und dann mit dynamischen Arrays (was genau den Listen in Python entspricht) beschäftigen.
Da Python (außer in der Bibliothek NumPy) keine Arrays unterstützt, werden wir hier zur Implementierung stattdessen Python-Listen verwenden. Hierbei beschränken wir uns aber auf die Operationen, welche auch bei gängigen Array-Implementierungen zur Verfügung stehen und werden auf mutierende Operationen wie Slicing, das Einfügen und Entfernen von Elementen verzichten. Einzig beim Anlegen einer neuen Liste werden wir diese schrittweise durch Anhängen von Elementen erweitern, was sich ein wenig vom Erzeugen eines Arrays gegebener Größe in anderen Programmiersprachen unterscheidet.
Obwohl wir zur Implementierung Python-Listen verwenden, werden wir im Folgenden immer den Begriff “Array” verwenden, um klarzustellen, dass wir eigentlich eine statische (nicht dynamisch erweiterbare) Datenstruktur meinen.