Data structure

0 like 0 dislike
39 views
Tell me the data structure for which:
  • Insertion time: guaranteed O(1) (preferably at a speed of insertion in linked list)
  • Access time to any item by its number in the list is also guaranteed to be O(1) (preferably with speed of access to array element)

The structure holds pointers or integers. The other operations does not matter.
by | 39 views

4 Answers

0 like 0 dislike
I think the only option with the expected O(1) hash table. If the data is known, it is possible to find a perfect hash function and then O(1) will be guaranteed.
by
0 like 0 dislike
by
0 like 0 dislike
eemmm. I'm afraid to embarrass myself in full view of the entire region, but... a dynamic array?
by
0 like 0 dislike
A hash table is probably the best option. To eliminate conflicts, replace each element of a list, or do open addressing.
by

Related questions

110,608 questions
257,186 answers
0 comments
32,905 users