List with amortized constant or logarithmic insertion: how fast can you search?

Question

Everyone knows (or needs to know) that it is impossible to create a list data structure that supports both the O (1) nesting in the middle and O (1).

For example, related list support is O (1), but O (N) is for searching, while arrays support O (1) for searching, but O (N) is for inserting (perhaps to depreciate O (1) for inserting end or both).

However, suppose you are ready to exchange O (1) with:

• Depreciation O (1)
• O (log (N)) insert

Then what is the theoretical assessment of the search in each of these cases? Do you know existing data structures? How about memory complexity?

Answer 1

These are still open problems, but the best grades that I know of are for Arne Andersson A non-multiplication subharithmic search that has inserts, deletes, and O searches (sqrt (lg (n))). However, this is due to an additional 2 K space, where k is the number of bits in integers stored in the data structure, which is why we still use balanced binary trees instead of the Andersson data structure. The data structure option allows you to search for O (1), but then the additional space increases to n2 ^ k, where n is the number of elements in the data structure. The randomized version does not use any additional space, but then the insert / delete / search time sqrt (lg (n)) becomes the average space time, and not the worst time time.

Answer 2

Tree-based data structures, such as a rope or finger tree , can often provide logarithmic insertion times at arbitrary positions. Compromise is access time, which is also logarithmic, except in special cases, such as fingertips.

Dynamic arrays can provide amortized constant insertion at the ends, but insertion in the middle requires copying part of the array and is O (N) in time, as you mentioned.

It is possible to implement a data structure that supports a depreciated constant average insert. If you add to either end, consider it as a dynamic array. If pasted in the middle, save the old array and add a new array “above” that contains the new “middle” list, using the old array for the data that is to the left or right of the middle. The access time will be logarithmic after the first average insertion and will keep track of which data was in which layer quickly becoming complicated.

It may be the "tiered" dynamic array mentioned in the wikipedia article, I have not explored it yet.

I suspect that no one really uses a data structure such as the fact that the middle insert is rarely found when you most need it, and the logarithmic insert (using trees) is good enough for most real-world cases.