The order maintenance problem (or maintaining order in a list) is to support the operations:singleton: creates a list with one item, returns a pointer to itinsertAfter: given a pointer to an item, inserts a new item after it, returning a pointer to the new itemdelete: given a pointer to an item, removes it from its listminPointer: given two pointers to items in the same list, returns the one closer to the front of the listI am aware of three solutions to this problem that perform all operations in $O(1)$ amortized time. They all use multiplication.Athanasios K. Tsakalidis: Maintaining order in a generalized linked listDietz, P., D. Sleator, Two algorithms for maintaining order in a listMichael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, and Jack Zito, Two Simplified Algorithms for Maintaining Order in a ListCan order be maintained in a list in $O(1)$ amortized time without using any arithmetic operations not in $AC^0$?
Maintaining order in a list in $AC^0$ in $O(1)$ time
ds.data structures
Yes!Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.See also exercise 8.12 from open data structures and Roura's A new method for balancing binary search trees.