A Bounded Storage Algorithm for Copying Cyclic Structures

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.

CACM June, 1977

Robson J. M.

copying, shared subtrees, cyclic structures

4.49 5.25

CA770609 JB December 28, 1977  12:56 PM

2766	4	2954
2855	4	2954
2954	4	2954
2954	4	2954
3106	4	2954
3106	4	2954
2665	5	2954
2766	5	2954
2954	5	2954
2954	5	2954
2954	5	2954
3106	5	2954
1549	6	2954
210	6	2954
1972	6	2954
2665	6	2954
2766	6	2954
2855	6	2954
2954	6	2954
2998	6	2954