Does there exist a data structure for quick list manipulation and order queries?

Question

We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$. Each element from $N$ appears in a single list in $L$. I am looking for a data structure which can perform the following updates:

1. $concat(x, y)$ : concatenates the list containing $y$ onto the end of the list containing $x$

2. $split(x)$ : splits the list containing $x$ directly after $x$

It also needs to perform the following queries:

1. $follows(x, y)$ : returns $true$ if $x$ and $y$ are in the same list and $y$ comes after $x$ (but is not necessarily adjacent to $x$)

2. $first(x)$ : returns the first element of the list containing $x$

3. $next(x)$ : returns the the next element after $x$ in the list containing $x$

I have already come up with a data structure which performs these updates in $O(lg^2 (n))$ and queries in $O(lg (n))$ time. I'm mostly interested in whether or not there is already a data structure which can do this (hopefully faster?).

Motivation: rooted directed forests can be represented with two of these list sets and they allow quick calculation of reachability in such forests. I want to see what else they can be used for and if all of this is already known.

Answer 1

Keep your integers in skip lists. Normal skip lists are ordered by key, but we will just use them as a representation of sequences. Additionally, maintain an array of pointers of size $n$. Each element of the array should point to a node in a skip list. I believe this supports $next$ in $O(1)$ and all other operations in $O(\lg n)$.

Specifically:

• $concat$ing or $split$ting two skip lists takes $O(\lg n)$ time and therefore invalidates at most $O(\lg n)$ pointers.
• $next$ just follows the forward pointer at the leaf level, taking $O(1)$ time.
• $first$ takes $O(\lg n)$ time: follow up pointers until you get stuck, then follow a left pointer. When you can't follow any more left pointers, you're at the head pointer of your skip list. Follow down pointers to the leaf, then one forward pointer. This is the first element in the list.
• $follows$ is somewhat trickier. Proceed as in $first$ for $y$, but record a list of the values where you get stuck (that is, where you can't follow up pointers any more). We'll call this list you record a "trace". Do the same for $x$, but follow right pointers when you get stuck, not left. If $x$ precedes $y$, their traces will intersect. The traces are of size $O(\lg n)$. If each element in the trace is annotated with the stuck level, we can check for an intersection in time $O(\lg n)$.

$next$ is worst-case $O(1)$, all others are $O(\lg n)$ with high probability. They can be made worst-case by using deterministic skip lists.

I think $concat$ can be made $O(\lg \lg n)$ by using leaf-level-linked (2,5) trees and boostrapping the spines. For the bootstrapping trick, see "Purely functional representations of catenable sorted lists" by Kaplan and Tarjan.

Answer 2

The least common ancestor problem can be used to solve the reachability problem in dynamic rooted trees, so I imagine you will also be interested in the following: Optimal Algorithms for Finding Nearest Common Ancestors in Dynamic Trees, by Alstrup and Thorup. This paper gives a time bound of $O(n + m \log \log n)$ for $n$ links and $m$ nca queries on a pointer machine.