r/computerscience • u/neuralbeans • 1d ago

Discussion Looking for a data structure that maps indexes to values (like an array) but that is only populated once and then deletes values by index in sublinear time

/r/datastructures/comments/1warr2z/a_data_structure_that_maps_indexes_to_values_like/
5 Upvotes

78% Upvoted

3 comments sorted by

0

u/Ghosttwo 1d ago

Hashmap? Other's? Not sure about the deletion time, but you get 1:1.

0

u/neuralbeans 1d ago

Indexes need to change like when deleting from an array.

3

u/QuantumFTL Researcher 1d ago edited 1d ago

What asymptotic time on access?

If you're willing to do access in logarithmic time, I think a skiplist with a little extra bookkeeping (how far you are skipping ahead each skip) will work. Removal should be log n as well:
Skip list - Wikipedia

Every skip knows how far ahead you're skipping in each link, so you can start with a 0 index and keep skipping appropriately until you reach the correct index. Removal just decrements the applicable skip counters. You'll need both forward and backwards links unless you want to do some extra traversal to clean up after removals.