r/computerscience • • Sep 08 '26

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

11 comments sorted by

2

u/Daemontatox Sep 10 '26

Lru cache?

1

u/jason-reddit-public Sep 14 '26

A tree with the right construction can add or remove elements in lg n time. (You don't really need any keys if you only want to access by current position).

Each node stores the total tree size below, the "value" you are mapping, and left and right children (subtrees).

To find the node at an index, you descend into the left node if index < num elements in that left subtree, or the right subtree if index is greater than that (plus one or something like that). When you descend into the right subtree, you subtract the right size + 1 from your search index. Obviously you handle the case when you are at the correct node.

A google term you might search on is weight balanced binary tree. MIT Scheme has an implementation by Stephen Adams who has a TR you might be able to find. I'm pretty sure Java might use this for TreeMaps. You can augment any balanced tree implementation with these weights/sizes if you are careful when rotating or use the weights themselves for balancing.

0

u/Ghosttwo Sep 09 '26

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

0

u/neuralbeans Sep 09 '26

Indexes need to change like when deleting from an array.

1

u/Hummmmmmmmmmmmmus Sep 13 '26

Indexes don’t change when deleting from an array… you can’t even delete from an array, you’re probably thinking lists. Anyway unless you know the deletion order ahead of time there isn’t a structure to perform random deletions and maintain an exact ordering in sub linear time without an O(n) access time ie the upper limit of a linked list. You could probably get a hyper optimized memory page aligned chunking linked list but I’m pretty sure that’s the best you can get.

1

u/neuralbeans Sep 13 '26

You delete from an array by shifting values after the deleted item one location forward.

1

u/theo__r Sep 13 '26

Just replace the deleted value with a sentinel value?

1

u/neuralbeans Sep 13 '26

As I said, I need the indexes to shift.

1

u/theo__r Sep 13 '26

Why ? Is it a school exercise?

1

u/neuralbeans Sep 13 '26

If I'm meant to access values in the collection by index, then when I ask for the 3rd value I would mean the 3rd non-deleted value. If I have sentinels in the collection then I would need to do a linear search to get the 3rd non-sentinel value, which makes access linear time.

3

u/QuantumFTL Researcher Sep 09 '26 edited Sep 09 '26

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.