Dietz, P., D. Sleator, Two algorithms for maintaining order in a list, Carnegie Mellon University Computer Science technical report CMU-CS-88-113, 1988.
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 records 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, but is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time.