A fast algorithm for copying list structures

ABSTRACT

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 auxillary 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.

REFERENCES

• 1: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 2: Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976 [doi>10.1145/360238.360247]
• 3: Douglas Wells Clark, List structure: measurements, algorithms, and encodings., 1976
• 4: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 5: David A. Fisher, Copying cyclic list structures in linear time using bounded workspace, Communications of the ACM, v.18 n.5, p.251-252, May 1975 [doi>10.1145/360762.360764]
• 6: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 7: Gary Lindstrom, Copying list structures using bounded workspace, Communications of the ACM, v.17 n.4, p.198-202, April 1974 [doi>10.1145/360924.360936]
• 8: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 9: J. M. Robson, A bounded storage algorithm for copying cyclic structures, Communications of the ACM, v.20 n.6, p.431-433, June 1977 [doi>10.1145/359605.359628]
• 10: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

General Terms:
Algorithms, Languages

Keywords:
Lisp, constant workspace, list copying, space complexity