iman12
Reputation: 1
A Data structure with delete o(1) and random access o(1)
I was looking for a data structure with delete o(1) and random access o(1) for my project. Could anybody help ?
Upvotes: 0
Views: 844
Answers (2)
Matt Timmermans
Reputation: 59144
If you insist on those complexities and you don't have to release memory in the table as soon as keys are deleted, then you can use dynamic perfect hashing.
It's a little complicated: https://en.wikipedia.org/wiki/Dynamic_perfect_hashing
To get O(1) deletes you'll have to defer any rehashes caused by delete until the next insert.
Upvotes: 1
Related Questions
- Data structure: insert, remove, contains, get random element, all at O(1)
- Data structure that supports the following in O(1) time: initialization, insertion, deletion, finding an element, deleting all elements
- Ordered list with O(1) random access and removal
- Data structure that supports random access by index and key, insertion, deletion in logaritmic time with order maintained
- Design a data structure with insertion, deletion, get random in O(1) time complexity,
- Data structure supporting O(1) remove/insert/findOldest?
- Data structure that allows accessing elements by index and delete them in O(1)
- Which data structure supports efficient deleting and random access?
- Iterable O(1) insert and random delete collection
- What data structure for O(1) random insertion/deletion and O(1) random access?