Copying cyclic list structures in linear time using bounded workspace

1 May 1975

journal article
Published by Association for Computing Machinery (ACM) in Communications of the ACM

Vol. 18 (5) , 251-252
https://doi.org/10.1145/360762.360764

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 n ² 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.

Keywords

LIST STRUCTURES
LINEAR TIME
WORKSPACE
BITS
SUP
COPYING
CONTIGUOUS
NODES

This publication has 1 reference indexed in Scilit:

Copying list structures using bounded workspace
Communications of the ACM, 1974