Categories
Game Development

One of those rare cases where a linked list is the best data structure

I have a B+ tree containing pointers, sorted by key. I had a queue which mirrored that tree, but was ordered by a fixed-interval timestamp (from most recent to least recent). I recently encountered a situation where I was able to look up the pointer by the key in the B+ tree, but didn’t know […]

I have a B+ tree containing pointers, sorted by key. I had a queue which mirrored that tree, but was ordered by a fixed-interval timestamp (from most recent to least recent). I recently encountered a situation where I was able to look up the pointer by the key in the B+ tree, but didn’t know its index into the queue. Since the queue could be tens of thousands of elements long, and the same op. had to be repeated many times, it was too slow to stick with. So I changed to a linked list. That way I could remove from the middle of the queue and readd at the head of the queue without scanning the queue for its index.

One reply on “One of those rare cases where a linked list is the best data structure”

Leave a Reply to Simon Wittber Cancel reply

Your email address will not be published. Required fields are marked *