@Nikolas: Listen sind als dynamische Arrays implementiert und Dictionaries als Hash-Tabellen. Benötigt also beides beim Zugriff auf Elemente O(1) Zeit.
Wie sieht denn die Speicherverwaltung für ein dynamisches Array mit Aktionen in konstanter Zeit aus? Wenn ich zusätzliche Objekte hinzufüge, muss doch entweder das komplette Array umkopiert werden, oder an einer zweiten Stelle zusätzlicher Platz bezogen werden.
Warum kann dann ein Array aber unterschiedliche Objekttypen aufnehmen? Besteht das Array dann aus einer Liste von Speicheradressen (array of Pointer), oder wie muss ich mir das vorstellen?
Erwarte das Beste und sei auf das Schlimmste vorbereitet.