Und damit kommen wir zu dem Thema dynamische Speicherverwaltung, die wir hier mit dem Beispiel

einer verketteten Liste einführen wollen.

Um verkettete Listen nochmal kurz aufzufrischen, hier eine kurze Übersicht, wann man sie verwendet.

Eine verkettete Liste braucht man immer dann, wenn man Dinge in einer Reihenfolge speichern

möchte und vorher nicht weiß, wie viel man eigentlich in dieser Liste abspeichern möchte.

Die Anforderungen an eine verkettete Liste, die sich damit ergeben sind, man weiß nicht,

wie viele Listelelemente überhaupt gespeichert werden sollen.

Das heißt, ich weiß nicht, wie viele Elemente gleichzeitig in der Liste liegen und ich weiß

auch nicht, wie viele Elemente über die gesamte Lebensdauer der Liste abgespeichert werden.

Das hat zur Folge, dass ich ebenfalls nicht weiß, wie lange ein Listelelement überhaupt

verfügbar sein muss.

Außerdem weiß ich nicht, wer alles Zugriff auf ein Listelelement haben soll.

Das bedeutet, wir brauchen irgendeinen Mechanismus, mit dem wir es leisten können, Listelelemente

zur Laufzeit des Programmes in beliebiger Anzahl neu zu erstellen und wieder zu zerstören,

da wir nicht wissen, wie viele Listelelemente wir insgesamt brauchen werden.

Um dies an einem Beispiel darzustellen, machen wir jetzt eine kleine Darstellung zwischen

der euch schon bereits bekannten Programmier Sparrett-Sharver und C und dies an einem Beispiel

aus Algorithmen und Datenstrukturen im Sommersemester 2011.

In Scharver kann eine verkettete Liste zum Beispiel so implementiert werden.

Man erstellt eine neue Klasse, in diesem Beispiel zum Beispiel WaitingHuman, um eine Menschenkette

zu implementieren.

Und die Klasse verfügt über ein Attribut, das die jeweils nächste Person in der Reihe

abspeichert.

In dem Beispiel wird über den Konstruktor eine neue Instanz der Klasse WaitingHuman

instanziert und hier wird ein Name gegeben.

Anschließend können zwei Instanzen einander gekettet werden, in dem die Add-Methode der

Klasse WaitingHuman aufgerufen wird.

Das interessante an der Stelle ist die Instanzierung einer neuen Klasse.

Hier wird mittels des New Operators eine neue Instanz erstellt und der New Operator leistet

an der Stelle zwei Dinge.

Auf der einen Seite reserviert er den notwendigen Speicher für das Objekt.

Gleichzeitig jedoch initialisiert er das Objekt durch ausführen des Konstruktors.

Das bedeutet, der durch New angeforderte Speicher wird gleichzeitig auch mit sinnvollen Werten

belegt.

Wenn wir jetzt einen C neuen Speicher allokieren wollen, dann geschieht dies mittels der malloc

Funktion.

Das heißt, wenn wir Platz für ein neues Listenelement allokieren möchten, dann können wir das machen

wie folgt.

Wir rufen malloc auf und geben als Argument die Anzahl an Bytes, die wir reservieren wollen.

In diesem Fall machen wir das mit dem sizeOf-Operator, der uns für die Struktur ListElement die Größe

in Bytes zurückliefert.

Der Rückgabewert der malloc Funktion ist schließlich ein Zeiger auf ein Stück Speicher, das mindestens

so groß ist wie von uns angefordert.

Was an der Stelle jetzt noch fehlt im Vergleich zu Java ist die Initialisierung des Speichers.

Im Moment ist dieser Speicher, der von malloc zurückgegeben wurde, nicht initialisiert

und hat damit undefinierte, sprich zufällige Werte.

Was an dieser Stelle ebenfalls fehlt, ist noch die Fehlerbehandlung.

Die malloc-Operation kann potenziell fehlschlagen.

Das bedeutet, wenn uns kein Speicher mehr zur Verfügung steht, kann die malloc-Funktion

auch keinen neuen Speicher zurückgeben.