I don't believe that bookkeeping would work very well. I think with very many inserts you'd quickly end up with nothing more than a linked list that wastes a a lot of memory. But I would honestly be delighted if you could prove me wrong. I'm not completely sure I'm right, I just haven't been able to come up with an algorithm in my head that would really make sense. I mean, I am wrong a lot, an awful lot of the time, but I'm going out on a limb here and saying there's no way you can implement that random access linked list you're talking about there. It would be squirrelly as all get-out, and it would quickly devolve into a mess where the accesses are indeed O(n). So I dare you to try and implement an example.