I'm trying to design a data structure that supports the following operations in $O(1)$ time:
- $\operatorname{query}(\ell)$: Yield some auxiliary datum associated with list $\ell$ (just a single integer for my use case).
- $\operatorname{update}(\ell,v)$: Set the auxiliary datum of list $\ell$ to $v$.
- $\operatorname{list}(n)$: Get the list associated with node $n$.
- $\operatorname{ends}(\ell)$: Get the end nodes of list $\ell$.
- $\operatorname{concat}(n_0,n_1)$: Concatenate $\operatorname{list}(n_0)$ and $\operatorname{list}(n_1)$ so that nodes $n_0$ and $n_1$ are adjacent. Preconditions are that $n_0$ and $n_1$ are end nodes in two distinct lists and those two lists have the same auxiliary data (which becomes the auxiliary datum of the resulting list).
- $\operatorname{split}(n)$: Split $\operatorname{list}(n)$ after node $n$ (according to some arbitrary assignment of direction to the lists). The resulting two lists have the same auxiliary data as the original list.
Use a model as powerful as you want, eg, word RAM.
Basically these are just linked lists with some additional data. The tricky part is to ensure the datum for a list can be updated in $O(1)$ but also accessed from any node in $O(1)$.
I was unable to do this with only elementary data structures like arrays and linked lists. The naive strategies I can think of run in $O(N)$ time (where $N$ is the maximum total number of nodes over the lifetime of the data structure). I think any balanced BST can yield a working solution$^1$, but that's $O(\log N)$ and the approach I'm thinking of does not lend itself well to using standard library BST containers, which is a pain. I'm hoping that this can be done in $O(1)$ in a simple-to-implement way. Something like $O(\log^\ast N)$ or $O(\alpha(N))$ would be good as well, and I would even be interested in a simple $O(\log N)$ strategy that doesn't require implementing a balanced BST from scratch.
$^1$: The idea for implementing these operations with BSTs is to let the key of a node in the tree be its rank in the current list ordering. The $\operatorname{split}$ and $\operatorname{concat}$ operations can change that ordering so we just have to let the structure of the trees represent the ordering implicitly. In all BST implementations that I'm aware of, the balancing, $\operatorname{split}$, and $\operatorname{concat}$ operations don't compare keys explicitly but just look at the tree structure so this works.
For the particular application that originally inspired this, the nodes come from a constant universe $U=\{0,1,\dotsc,N-1\}$ and represent vertices in a rooted tree such that, at any given point, all lists will be descending paths in the tree. This makes the BST strategy particularly simple to implement: the key ordering is the (fixed) ordering by depth.
ends
operation. As for construction it didn't seem important but you can imagine acreate()
operation that returns a list consisting of a single new node. $\endgroup$create()
operation and then accessing them later. For my use case the nodes correspond directly to vertices in a given tree and the user could just store them in an array. $\endgroup$n
? What range isn
? Use hashing on the keyn
? $\endgroup$n
mostly means node, not integer. I unfortunately chose to usen
to also represent the total number of nodes over the use of this data structure, but I've rewritten things to useN
to represent that instead. $\endgroup$