PADDED LISTS REVISITED

被引:5
作者
HOFRI, M [1 ]
KONHEIM, AG [1 ]
机构
[1] UNIV CALIF SANTA BARBARA,DEPT COMP SCI,SANTA BARBARA,CA 93106
关键词
COMPUTER OPERATING SYSTEMS;
D O I
10.1137/0216069
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study a data structure L referred to variously as a padded list, controlled density array or sparse table containing records left brace R//i right brace each uniquely identified by a key left brace k(R//i) right brace . L is required to support the operations Search (L, k), Insert (L, k) and Delete (L, k) to search, insert and delete a record with key k. To optimize Search (L, k), records are stored with their keys in sorted order. If the order of the keys is to be maintained under insertion, records currently in L must be moved to free space. To improve the efficiency of Insert (L, k), records are stored in a circular buffer with 'gaps' so that insertion necessitates moving only records up to the next gap. The array is expanded and contracted during a sequence of insertions and deletions depending upon the current number of gaps. In this paper we assess the amount of work required to insert a sequence of records.
引用
收藏
页码:1073 / 1114
页数:42
相关论文
共 7 条
[1]  
Ahlfors L. V., 1953, COMPLEX ANAL
[2]  
Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st
[3]  
FRANKLIN WR, 1979, INFORM PROCESS LETT, V9, P161, DOI 10.1016/0020-0190(79)90060-7
[4]  
ITAI A, 1980, IBM8550 RES REP
[5]  
MELVILLE R, 78362 CORN U TECHN R
[6]  
Reingold E. M., 1977, COMBINATORIAL ALGORI
[7]   DATA STRUCTURE FOR MANIPULATING PRIORITY QUEUES [J].
VUILLEMIN, J .
COMMUNICATIONS OF THE ACM, 1978, 21 (04) :309-315