On the complexity of a "list" datastructure in the RAM model

Question

I am interested in the complexity of a data-structure equipped with the following operations (similar to a list):

1. insertion of an element at a given position within the list
2. deletion of an element at a given position within the list
3. get the value of an element at a given position within the list

For instance "insert $v_3$ at position 3"; modifies the list $e_1 e_2 e_3 e_4$ into $e_1 e_2 v_3 e_3 e_4$ and "delete at position 4" would produce the list $e_1 e_2 v_3 e_4$.

Obviously a list can be used to answer all these questions but with a $O(n)$ complexity for all three operations. We can also use an array to have 3. with $O(1)$ complexity but with $O(n)$ complexity for 1. and 2. Finally we can use a balanced tree structure to get all three operations in $O(\ln(n))$. Is there any other known structure that achieves an interesting compromise?

A second but related question: If the operation 3. is limited to retrieve the value of the first element, can we do any better than this? Of course for this a list achieves $O(n)$ for 1. and 2. but $O(1)$ for the first element. With a bit of modification I think we can make the array-based solution work in $O(n)$ for deletion of the first element but $O(1)$ for everything else. With the balanced tree approach we can make $O(\ln(n))$ for 2. and 3. and $O(1)$ for 1. Are there any structure with a better compromise here?

Finally a third (and last) question, when 3. is limited to ask for the first element, what is the best that can be achieved for the sum of the complexities of 1., 2. and 3.? Are there any known lower bounds for this? Is there a better upper bound than $O(\ln(n))$?

Answer 1

It appears that all of these operations can be performed in time $O(\log n/\log\log n)$ on a RAM, by combining methods for maintaining a dynamic labeling of the list elements by integers of polynomial magnitude (e.g. Bender et al, "Two Simplified Algorithms for Maintaining Order in a List", ESA 2002, https://erikdemaine.org/papers/DietzSleator_ESA2002/) with methods for ranking and unranking sets of small integers (Pătraşcu and Thorup, "Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search", FOCS 2014, https://arxiv.org/abs/1408.3045).

Operation 3 (get the value at a given position) is the simplest: it's just unranking. To insert or delete at a given position, use unranking to find which list element is there, do the insert or delete operations in your list at or near that element, use the order-maintenance structure to modify the numbering of elements, and then update the ranking-and-unranking data structure according to those modifications.

Update 2020-05-25: Kasper Green Larsen emailed me the following lower bound proof and suggested I post it here:

We can prove the following lower bound: Let $t_u$ denote the update time and $t_q$ the query time of a data structure for the list problem. Both are worst case times. Then we have the following lower bounds (when the word size is logarithmic): If $t_u$ is polylog$(n)$, then $t_q = \Omega(\log n/\log\log n)$. If $t_q$ is polylog$(n)$, then $t_u = \Omega(\log n/\log\log n)$.

The proofs follow by reduction from 1-bit partial sums; see Pătraşcu and Demaine (SODA'04) [DE: See also Fredman and Henzinger, "Lower bounds for fully dynamic connectivity problems in graphs", Algorithmica 1998]. In 1-bit partial sums, we have a bit vector of length $n$. An update flips the value of a bit. A query asks for the parity in a prefix of the array. In that paper, they prove exactly the above lower bounds for 1-bit partial sums, although their lower bound also holds if we change to amortized update and query time. The reduction I have loses that property (it can probably be fixed, see comment at the end). To give the reduction, we need to carefully examine the proof of Pătraşcu and Demaine to realize that their lower bound for partial sums holds even if the data structure is allowed to perform an arbitrary amount of preprocessing before seeing any updates or queries, as long as the word size is logarithmic, we have the lower bound (this observation is not necessary for the fix for amortized vs worst case). The initial input array in partial sums is all-0s and the sequence of operations for which they prove their lower bounds has only $n$ operations on the array.

We will reduce from 1-bit partial sums in an array of size $\sqrt n$ (and thus only $\sqrt n$ operations in the hard sequence) to the list problem in a list of up to $n$ elements. It goes as follows: As a preprocessing step, set the list to contain $\sqrt n$ batches of the numbers $0,\dots,\sqrt{n} - 1$, i.e. the list looks like:

$$0,1,\dots,\sqrt{n}-1,0,1,\dots,\sqrt{n}-1,\dots,0,1,\dots,\sqrt{n}-1$$

with a total of $n$ elements.

Upon an update to flip the $i$th bit of the partial sums array, we remove element $i \sqrt n$ from the list.

To compute the prefix sums up to index $i$ in the array, we retrieve element $i\sqrt n$ from the list and return its parity.

Let us see that the reduction works. First observe that before any updates are made to the list, a prefix sums query for an index $i$ will retrieve the "0" element in the $i$th batch. Moreover, since we have only $\sqrt n$ operations, and all operations remove at most one element from the list, a prefix sums query for element $i$ will always retrieve an element that comes from the original $i$th batch. Finally, observe that when we delete the $(i\sqrt n)$th element of the list, all prefix sums queries for entries $j<i$ are unaffected since the first part of the list doesn't change. Also, for all queries $j\ge i$, we will now return the next element of the list since the list indices on or after $i\sqrt n$ all change by one. This next element will come from the same original batch and have a value one larger than before because we haven't deleted from this part of the original batch (this is where we use that we have $\sqrt n$ copies in each batch). Thus the answers to all queries $j\ge i$ correctly have their parity flipped.

The lower bound for 1-bit prefix sums on arrays of size $\sqrt n$ is the same as on arrays of size $n$ since $\log n$ only changes by a factor $2$. Also, the lower bound holds even if we ignore all time that was spend during preprocessing, so we get our sought lower bound.

The reason why we lose the amortized lower bound is that we need to do $n$ initial operations to create the list. Thus even if we spend $\sqrt n$ time on each of the operations after preprocessing, the amortized time to process the whole sequence is only $O(1)$ per operation. This can probably be fixed as follows: Run $\sqrt n$ copies of the hard distribution for 1-bit partial sums, where after each sequence of $\sqrt n$ operations, we re-insert all elements that have been deleted. Then we get a total of $n$ updates and queries that all have a large amortized lower bound from 1-bit prefix sums. This is not completely formal, but I'm certain it can be formalized.

Answer 2

I understand you may only be interested in purely theoretical answers, but all theory are based on an underlying model. If your model is that all memory can be addressed in O(1) time, then these alternative data structure are of interest.

Otherwise, I always advise people to use arrays. If you need to add items, add them at the end in O(1) time. If you need them ordered, then sort the array, but only afterward, once it has been filled. Similarly, if you need to remove elements, it is better to wait to do it in batch. IOW, accumulate linearly elements (or their indices) to be deleted in another array. Then recreate the original array in a new one by linear insertion at the end, skipping the elements to be removed. (And then sort, if needed.)

The main error to be done is to design algorithms to work on a single element at a time and analyze complexity at the single-element operation level. Doing operations in batches, processing the maximum number of items linearly is better, 99% of the time.