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