Two algorithms for maintaining order in a list 论文

详细信息

发表日期

1987-01-01

发表年份

1987

摘要

The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two elements comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O(1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time.