A Fast Algorithm for Copying List Structures An algorithm is presented for copying an arbitrarily linked list structure into a block of contiguous storage locations without destroying the original list. Apart from a fixed number of program variables, no auxiliary storage, such as a stack, is used. The algorithm needs no mark bits and operates in linear time. It is shown to be significantly faster than Fisher's algorithm, the fastest previous linear-time algorithm for the same problem. Its speed comes mainly from its efficient list-traversal technique, which folds the processing stack into the structure being built, and from its classification of list cells into nine types, which enables processing operations to be optimized for each type. CACM May, 1978 Clark, D. List copying, Lisp, space complexity, constant workspace 4.34 4.49 5.25 CA780501 DH February 26, 1979 3:25 PM 1024 4 3106 1051 4 3106 1102 4 3106 1132 4 3106 1390 4 3106 1486 4 3106 1549 4 3106 1706 4 3106 1826 4 3106 1869 4 3106 1878 4 3106 378 4 3106 2060 4 3106 2155 4 3106 2156 4 3106 2168 4 3106 2361 4 3106 2513 4 3106 2513 4 3106 2665 4 3106 2719 4 3106 2723 4 3106 2723 4 3106 2736 4 3106 2766 4 3106 2838 4 3106 2842 4 3106 2855 4 3106 2855 4 3106 2855 4 3106 2855 4 3106 2855 4 3106 2879 4 3106 2944 4 3106 2954 4 3106 2954 4 3106 3074 4 3106 3077 4 3106 3080 4 3106 3106 4 3106 3106 4 3106 3106 4 3106 3106 4 3106 3106 4 3106 3106 4 3106 3106 4 3106 3106 4 3106 3112 4 3106 627 4 3106 106 4 3106 210 5 3106 1549 5 3106 1972 5 3106 2665 5 3106 2766 5 3106 2855 5 3106 2954 5 3106 2998 5 3106 3106 5 3106 3106 5 3106 3106 5 3106