Lektion 73:

Verkettete Liste

Bisher 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:

class Element
{
   private:
      int m_wert;
      Element *m_pNeachstesElement;
};

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

   Element *pNeuesElement=new Element;
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

   *pNeuesElement.m_wert=4;
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

   *pNeuesElement.m_pNeachstesElement=pStart;
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

   pStart=pNeuesElement;
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

   Element *pZuLoeschendesElement=pStart;

Dann wird der Listenanfang auf das nächste Element gelegt mit

   pStart=*pStart.m_pNeachstesElement;

Und jetzt kann das zu löschende Element gelöscht werden mit

   delete pZuLoeschendesElement;


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