Data structure

Question

Algorithms

Suggest a data structure for which:

• Insertion time: guaranteed O(1) (preferably at the speed of inserting into a linked list)
• Access time to an arbitrary element by its number in the list is also guaranteed O(1) (preferably with the speed of access to an array element)

The structure will store pointers or integers. The running time of other operations does not matter.

Answer 1

In my opinion, the only option with the expected O(1) is a hash table. If the data is known, you can choose the perfect hash function and then O (1) will be guaranteed.

Answer 2

Fibonacci heaps ?

Answer 3

ummm. I'm afraid to embarrass myself in front of the entire district, but ... a dynamic array?

Answer 4

A hash table is probably the most suitable option. To eliminate collisions, replace each element with a list or do open addressing.