Copying list structures using bounded workspace
- 1 April 1974
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 17 (4) , 198-202
- https://doi.org/10.1145/360924.360936
Abstract
Two new algorithms are presented for list structure copying using bounded workspace. The first, of primarily theoretical interest, shows that without cell tag bits the task can be performed in time n 2 . The second algorithm, assuming one tag bit in each cell, delivers attractive practical speed. Any noncyclic structure is copied in linear speed, while cyclic structures are copied in average time less than n log n . No foreknowledge of cycle absence is necessary to achieve linear speed. A variation of the second algorithm solves an open problem concerning list structure marking. That result demonstrates that marking can be done in average time n log n without the aid of supplemental tag bits or stacks.Keywords
This publication has 4 references indexed in Scilit:
- Scanning list structures without stacks or tag bitsInformation Processing Letters, 1973
- A nonrecursive list moving algorithmCommunications of the ACM, 1973
- A Space-Efficient List Structure Tracing AlgorithmIEEE Transactions on Computers, 1972
- An efficient machine-independent procedure for garbage collection in various list structuresCommunications of the ACM, 1967