Copying cyclic list structures in linear time using bounded workspace

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Copying cyclic list structures in linear time using bounded workspace

Full text

Pdf (187 KB)

Source

Communications of the ACM archive
Volume 18 , Issue 5 (May 1975) table of contents

Pages: 251 - 252

Year of Publication: 1975

ISSN:0001-0782

Author

David A. Fisher

Institute for Defense Analyses, Arlington, VA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 10

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/360762.360764 What is a DOI?

ABSTRACT

A bounded workspace copying algorithm for arbitrary list structures is given. This algorithm operates in linear time and does not require tag bits. The best previous bounded workspace copying algorithms achieved n2 time without tag bits and n log n time with one tag. The only restriction on the algorithm given here is that the copy must be placed into a contiguous section of memory. The method is applicable to fixed or variable size nodes.

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.

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]

CITED BY 10

	Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976
	Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 1978
	David C. Luckham, A brief account: Implementation and applications of a Pascal program verifier (Position Statement), Proceedings of the 1978 annual conference, p.786-792, January 1978
	J. M. Robson, A bounded storage algorithm for copying cyclic structures, Communications of the ACM, v.20 n.6, p.431-433, June 1977
	K. P. Lee, A linear algorithm for copying binary trees using bounded workspace, Communications of the ACM, v.23 n.3, p.159-162, March 1980
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	Maurice P. Herlihy , Barbara Liskov, A Value Transmission Method for Abstract Data Types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.527-551, Oct. 1982
	Stanley Lee , Willem P. deRoever , Susan L. Gerhart, The evolution of list-copying algorithms and the need for structured program verification, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.53-67, January 29-31, 1979, San Antonio, Texas
	Phil McGachey , Antony L. Hosking, Reducing generational copy reserve overhead with fallback compaction, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994