Verkettete Listen: Modifikation (3)

Wenn wir vor  einem Einstiegselement auf analoge Weise ein Datenelement eintragen oder aber das Einstiegselement entfernen wollen, so brauchen wir dazu Zugriff auf den Vorgängerknoten des Einstiegselements, da sich dessen Nachfolger ändert; und diesen Zugriff können wir nicht billig bekommen, weil wir vom Listenanfang her suchen müssen. Es gibt allerdings einen Kunstgriff,  der die Tatsache ausnutzt, daß es uns auf die Datenwerte  und nicht auf die Listenknoten  ankommt; leider funktioniert er beim Löschen des letzten Listenelements nicht.

Beim Einfügen tragen wir das Einstiegselement als seinen eigenen Nachfolger  ein und überschreiben es dann mit dem neuen Datenwert: 

PROCEDURE einfuegevor(a: atom; VAR q: liste);
VAR p: liste;
BEGIN NEW(p);
      p^.wert := q^.wert; p^.nach := q^.nach; 
      (* oder besser: p^ := q^ *)
      q^.nach := p; q^.wert := a; q := p;
END einfuegevor;
Die letzte Anweisung bewirkt, daß der Zeiger q wieder auf den als Einstieg gebrauchten Datenwert  zeigt. Jetzt muß  q Referenzparameter sein, weil das Einstiegselement seinen Ort ändert!

Beim Entfernen überschreiben wir das Einstiegselement mit seinem Nachfolger, sofern  es einen solchen gibt, und löschen diesen. 

PROCEDURE entfernebei(VAR a: atom; q: liste);
VAR p: liste;
BEGIN p := q^.nach; 
      q^.wert := p^.wert; q^.nach := p^.nach;
      (* oder besser: q^ := p^ *)
      DISPOSE(p);
END entfernebei;
Der Verweis q ist anschließend ein dangling pointer; und das zu Recht, weil wir ja das darüber vorher zugängliche Einstiegselement gelöscht haben.

Gibt es keinen Nachfolger, wollen wir also das letzte Datenelemen der Liste löschen, so bleibt uns nichts anderes übrig, als vom Listenanfang her zu suchen, und dann haben wir (leider) linearen Aufwand bezüglich der Listenlänge.

zurück | Inhalt | Index | vor | Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36