A bounded storage algorithm for copying cyclic structures
- 1 June 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 20 (6) , 431-433
- https://doi.org/10.1145/359605.359628
Abstract
A new algorithm is presented which copies cyclic list structures using bounded workspace and linear time. Unlike a previous similar algorithm, this one makes no assumptions about the storage allocation system in use and uses only operations likely to be available in a high-level language. The distinctive feature of this algorithm is a technique for traversing the structure twice, using the same spanning tree in each case, first from left to right and then from right to left.Keywords
This publication has 2 references indexed in Scilit:
- Copying cyclic list structures in linear time using bounded workspaceCommunications of the ACM, 1975
- Copying list structures using bounded workspaceCommunications of the ACM, 1974