I'm trying to come up with a data structure that could access, insert, and delete any element in constant time. I know that's pretty difficult, but I'm just doing it to invoke thought and understanding about computer science. However, I'm starting to question whether it is even possible.
My theory is: For access to be in constant time, the data would need to be stored in a static location (like an array). And for insertion/deletion to be in constant time, the data would need to be stored dynamically using pointers or some sort of lookup table (like a linked list). Therefore, no data structure can have all three operations run in constant time.
Is this reasoning correct?
access(index): returns element at given index
insert(element, index): Inserts element into 'index' and shifts everything after 'index' right one index
delete(index): Removes element at 'index' and corrects indexes so that there are no gaps (i.e. shifts everything after 'index' left one index)