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:

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.

Idee der einfach verketteten Liste

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:

Ein Element am Endeder einfach verketteten Liste einfü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:

Ein Element irgendwo inder einfach verketteten Liste einfügen

Aufgabe 1

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

X

Fehler melden

X

Suche