Einfach verkettete Listen

Wozu brauchen wir Listen?

Arrays sind, wie wir gesehen haben, extrem zeiteffiziente Datenstrukturen. Wir können in konstanter Zeit (also unabhängig von der Länge des Arrays) auf jedes beliebige Datenobjekt in unserem Array zugreifen. Also kann man sich jetzt natürlich die Frage stellen, wozu wir überhaupt eine andere Datenstruktur brauchen, wenn das Array doch so schnell ist?

Schauen wir uns dazu die typischen Eigenschaften einer Liste an:

• Listen können gewöhnlich vollkommen willkürliche Datentypen speichern. Wir können eine Liste also mit Integers, Strings, ja sogar mit anderen Listen anfüllen und diese wild vermischen.
• Listen können beliebig erweitert werden. Wir können also anfangs mit einer leeren Liste beginnen und diese immer größer und größer werden lassen, indem wir immer mehr Datenobjekte anhängen oder einfügen
• Genau wie ein Array können wir uns auch die Liste so vorstellen, dass sie zum einen aus dem Speicher besteht, auf dem die Datenobjekte liegen, zum anderen aus dem Speicher, den wir benötigen, um unserem Compiler zu sagen, dass er es mit einer Liste zu tun hat und Zeigern, auf die Daten. Wenn wir aber nachträglich Daten hinzufügen können, können wir nicht von vorneherein Zeiger auf die Speicherbereiche einrichten, die wir benutzen wollen. Und dann stellt sich die Frage, wie wir im Endeffekt beliebig viel Speicher freilassen wollen, um beliebig viele Zeiger einzurichten, da wir beliebige Datenobjekte anhängen können. Stellt sich im Endeffekt gar heraus, dass wir bei Listen garnicht beliebig viele Objekte anhängen können?

Wie realisiert man eine solche Liste?

Natürlich stellt sich das nicht heraus, wir können (abgesehen natürlich von den physikalischen Beschränkungen, dass wir irgendwann keinen Speicherplatz mehr haben), beliebig viele Elemente anhängen.

Wir können allerdings natürlich nicht von vorneherein beliebig viel Speicher für unsere Liste reservieren, sonst wäre unser Speicher ja direkt voll.

Das heißt, wir müssen Speicher genau dann reservieren, wenn wir ein neues Datenobjekt zu unserer Liste hinzufügen. Da zwischen dem Hinzufügen zweier neuer Listenelemente allerdings natürlich Speicher frei geworden und/oder belegt worden sein kann, müssen wir nehmen, was auch immer gerade frei ist.

Da es dann nicht möglich ist, unseren Anfangsinformationen alle Zeiger mitzugeben, die wir eventuell brauchen, geben wir diesen nur genau einen Zeiger auf das erste Element unserer Liste mit (Platz für das erste Element müssen wir der Liste also automatisch mitgeben).

Die weiteren Informationen werden dann jedem einzelnen Element gegeben. Jedes Element bekommt also zusätzlich einen Zeiger auf das nächste Element im Speicher mitgegeben. Und das nächste auf das wieder nächste, usw.

Wir sehen, dass es vollkommen egal ist, wo im Speicher wir ein neues Listenelement platzieren, da unser Zeiger überall hin zeigen können. Wir können natürlich noch etwas Speicher sparen, indem wir die Information, dass es sich bei unserem Konstrukt um eine verkettete Liste handelt mit im Listenkopf speichern. Jetzt ist es natürlich ganz einfach ein Element am Ende der Liste einzufügen:

Wenn wir ein Objekt mitten in die Liste einfügen wollen, müssen wir allerdings nicht nur einen Zeiger hinzufügen (in dem Fall direkt zu unserem neuen Objekt), sondern auch einen alten Zeiger ändern, damit das Objekt an der richtigen Stelle in der Liste erscheint:

Aufgabe 1

Initialisiere eine Liste und messe (durch Timer), wie lange der Zugriff auf einige Elemente benötigt.