ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
A nonrecursive list moving algorithm
Full text PdfPdf (259 KB)
Source
Communications of the ACM archive
Volume 16 ,  Issue 5  (May 1973) table of contents
Pages: 305 - 307  
Year of Publication: 1973
ISSN:0001-0782
Author
Edward M. Reingold  Univ. of Illinois at Urbana-Champaign, Urbana
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 2,   Downloads (12 Months): 14,   Citation Count: 3
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/362041.362200
What is a DOI?

ABSTRACT

An efficient, nonrecursive algorithm is given for moving any LISP-type list. In particular, the algorithm requires no storage other than the new nodes into which the lists is to be moved, and no additional bits per node for marking; the algorithm runs in time proportional to the number of nodes in the list. The original list structure is destroyed as it is moved.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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
Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
3
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]

CITED BY  3
Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976
Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
Gary Lindstrom, Copying list structures using bounded workspace, Communications of the ACM, v.17 n.4, p.198-202, April 1974

INDEX TERMS

Keywords:
LISP, garbage collection, list copying, list moving, list traversal

Collaborative Colleagues:
Edward M. Reingold: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player