Mark/Sweep

Plan: wenn Speicher voll, dann:

• alle lebenden Zellen markieren
• alle nicht markierten Zellen in Freispeicherliste

Problem: zum Markieren muß man den Graphen durchqueren, man hat aber keinen Platz (z. B. Stack), um das zu organisieren.

Lösung:

H. Schorr, W. Waite: An efficient machine-independent procedure for garbage collection in various list structures, Communations of the ACM, 10(8):481-492, August 1967.

temporäre Änderungen im Graphen selbst (pointer reversal)