Two algorithms for maintaining order in a list
- 1 January 1987
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 365-372
- https://doi.org/10.1145/28395.28434
Abstract
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.Keywords
This publication has 0 references indexed in Scilit: