Access Restriction

Author Clark, Douglas W.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Space complexity ♦ Constant workspace ♦ Lisp ♦ List copying
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.
Description Affiliation: Xerox Palo Alto Research Center, Palo Alto, CA (Clark, Douglas W.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 5
Page Count 7
Starting Page 351
Ending Page 357

Open content in new tab

   Open content in new tab
Source: ACM Digital Library