Copying List Structures Using Bounded Workspace

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 nlogn.  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 nlogn without
the aid of supplemental tag bits or stacks.

CACM April, 1974

Lindstrom, G.

list processing, copying, marking, space complexity

4.34 5.25

CA740405 JB January 18, 1978  9:55 AM

1869	4	2665
2513	4	2665
2665	4	2665
2665	4	2665
2723	4	2665
2855	4	2665
3106	4	2665
1383	5	2665
1549	5	2665
2665	5	2665
2665	5	2665
2665	5	2665
2766	5	2665
2954	5	2665
3106	5	2665
1549	6	2665
210	6	2665
1972	6	2665
2665	6	2665
2665	6	2665
2665	6	2665
2766	6	2665
2766	6	2665
2855	6	2665
2954	6	2665
2998	6	2665