Copying list structures using bounded workspace

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Copying list structures using bounded workspace

Full text

Pdf (438 KB)

Source

Communications of the ACM archive
Volume 17 , Issue 4 (April 1974) table of contents

Pages: 198 - 202

Year of Publication: 1974

ISSN:0001-0782

Author

Gary Lindstrom

Univ. of Pittsburgh, Pittsburgh, PA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 11, 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/360924.360936 What is a DOI?

ABSTRACT

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 n2. 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 n log n. 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 n log n without the aid of supplemental tag bits or stacks.

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	Edward M. Reingold, A nonrecursive list moving algorithm, Communications of the ACM, v.16 n.5, p.305-307, May 1973 [doi>10.1145/362041.362200]
	2	Knuth, Donald E. Fundamental ,4lgorithms, Addison-Wesley, Reading, Mass., 1968.
	3	Lindstrom, Gary. Scanning list structures without stacks or tag bits, hzJi Proc. Letters 2, 2 (June 1973), 47-51.
	4	Wegbreit, Ben. A space-efficient list structure tracing algorithm. IEEE Traits. Comp. C-21, 9 (Sept. 1972), 1009-1010.
	5	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 10

	Manfred Broy , Peter Pepper, Combining Algebraic and Algorithmic Reasoning: An Approach to the Schorr-Waite Algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.362-381, July 1982
	Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 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
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	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
	Dorothea A. Klip, The variable cell length listprocessor VARLIST, Proceedings of the 1974 annual conference, p.128-132, January 1974
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	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
	R. J. R. Back , Heikki Mannila , Kari-Jouko Räihä, Derivation of efficient DAG marking algorithms, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.20-27, January 24-26, 1983, Austin, Texas
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994