My gut tells me there is no good way to achieve this, but, unlike Mr. Stephen Colbert, I'd rather trust a community of developers than my gut...
Is there a known way to efficiently implement a "best of both worlds" list, one that provides random access by index and O(1) insertion/removal like a linked list?
I foresee two possible outcomes: either "No, this is impossible, for the following obvious reasons..." or "Uh, yes, this has been done; see here, here, and here."