A data structure supporting O(1) random access and worst-case O(1) append?
There is a beautiful structure called an extendible array that has worst-case O(1) insertion and O(n) memory overhead (that is, it's asymptotically comparable to a dynamic array, but has O(1) worst-case insertion). The trick is to take the approach that the vector uses - doubling and copying - but to make the copying lazy. For example, suppose you have an array of four elements like this one:
[1] [2] [3] [4]If you want to add a new number, say 5, you begin by allocating an array that's twice as large:
[1] [2] [3] [4][ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]Next, you insert 5 into the new array:
[1] [2] [3] [4][ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]Finally, pull down the 4 from the old array into the new:
[1] [2] [3] [ ][ ] [ ] [ ] [4] [5] [ ] [ ] [ ]From now on, any time you do an insert, add the element to the new array and pull down one more element from the old array. For example, after adding 6, we'd get
[1] [2] [ ] [ ][ ] [ ] [3] [4] [5] [6] [ ] [ ]After inserting two more values, we end up here:
[ ] [ ] [ ] [ ][1] [2] [3] [4] [5] [6] [7] [8]If we now need to add one more element, we discard the now-empty old array and allocate an array twice as large as the current array (capable of holding 16 elements):
[1] [2] [3] [4] [5] [6] [7] [8][ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]And repeat this process. Discounting the cost of a memory allocation (which is usually sublinear in the size of the array), you do at most O(1) work per insertion.
Lookups are still O(1), since you just decide which of the two arrays to look in, while insertions in the middle are O(n) because of the shuffling.
If you're curious, I have a Java implementation of this structure on my personal site. I don't know how useful you'll find it, but you're more than welcome to try it out.
If you want to invest a bit of time reading over a research paper and trying to implement a fairly complex data structure, you can get the same result (worst-case O(1) append) in O(√n) space overhead (which is provably optimal, by the way) using the ideas in this paper. I never got around to actually implementing this, but it's certainly well-worth the read if memory is a super-scarce resource. Interestingly, it uses this above construction as a subroutine!
When I need a container like that, I use my implementation of the structure described in "Resizeable Arrays in Optimal Time and Space"
OK. What you have described is almost exactly what std::deque is in the C++ standard library. The difference is that an array(usually) is used to hold the pointers to the sub arrays instead of using a linked list.