Lektion 73:Verkettete ListeBisher waren Containerklassen im Wesentlichen nur Arrays. Arrays haben den Nachteil, daß ein Einfügen in ein bereits volles Array ein komplettes Neuanlegen eines größeren Speicherbereichs und das Kopieren aller Elemente erfordert. Das kann sehr lange dauern. Es gibt aber einen Trick, dies zu umgehen. Gegeben sei folgende Klasse:
Jedes Element hat also einen Wert und einen Zeiger auf das folgende Element. Die Elemente sind mit diesen Zeigern aneinandergehängt, wir sagen verkettet. Stellen Sie sich vor, drei solcher Elemente würden wie folgt im Speicher liegen: Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 Als Zusatzinformation braucht man nur zu wissen, daß diese Kette bei der Adresse 4711 beginnt. Wenn man sich das Element bei Adresse 4711 anschaut, dann sieht man, daß dort der Wert 3 steht, und man sieht, daß das nächste Element bei Adresse 4750 zu finden ist. Bei Adresse 4750 sieht man den Wert 2 und die Folgeadresse 4721. Dort sieht man der Wert 1 und die Folgeadresse 0. Die Adresse 0 hat in C++ eine ganz besondere Bedeutung: Dort kann kein Objekt stehen. Diese Adresse kann man also sehr gut dazu verwenden, um auszudrücken, daß dort kein weiteres Objekt steht, also hier, um zu sagen, daß die Kette hier zu Ende ist. Eine solche Datenstruktur wird verkettete Liste genannt. In diesem Beispiel sei die Adresse des ersten Listenelements immer in einer Variablen namens m_pStart gespeichert (Sie erkennen am "m_" sicher, daß eine entsprechende Klasse gebaut werden soll). Jetzt wollen wir vor die Liste ein neues Element mit dem Wert 4 einfügen. Ausgehend von der bisher bestehenden Liste Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 m_pStart==4711 erzeugen wir zuerst ein neues Element mit
Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 4770 ? ? pStart==4711 pNeuesElement==4770 Jetzt schreiben wir den neuen Wert in das neue Element mit
Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 4770 4 ? m_pStart==4711 pNeuesElement==4770 Es folgt die Verkettung mit dem Rest der Liste mit
Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 4770 4 4711 m_pStart==4711 pNeuesElement==4770 Dann wird der Anfang der Liste auf das neue Element gesetzt mit
Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 4770 4 4711 m_pStart==4770 pNeuesElement==4770 Und zum Schluß kann die Variable pNeuesElement wieder gelöscht werden. Adresse m_wert m_pNeachstesElement 4711 3 4750 4721 1 0 4750 2 4721 4770 4 4711 m_pStart==4770 Jetzt ist eigentlich nur noch herauszufinden, wie das erste Element gelöscht werden kann, und schon könnte man damit einen Stack implementieren. Zum Löschen muß man sich zunächst das zu löschende Element merken mit
Dann wird der Listenanfang auf das nächste Element gelegt mit
Und jetzt kann das zu löschende Element gelöscht werden mit
Falls Ihnen Fehler im Text auffallen oder Sie Verbesserungsvorschläge haben, dann schicken Sie mir bitte eine Mail. Ich werde mich dann sofort darum kümmern. [aktuelle Version] [inhalt] [index] [Fehlerkorrektur, Verbesserungsvorschlag] © Volkard Henkel <volkard@normannia.de>, last update: 08/25/00 |