Implementation of ArrayList

[pifrely]

I took a class in data structures some time back. In it, I learned that the ArrayList is an array that is just copied into a bigger array when space runs out. But instead of copying everything, even though it happens in amortized constant time, wouldn't it be better to represent it as a doubly linked list of arrays? When it exceeds the current capacity, you can add a new array that's twice as big as the previous one. Or better yet, an ArrayList of arrays, since you can access individual elements with just 2 []/get() operations, and you need to resize the ArrayList much less frequently (and copying comparably fewer elements each time). Of course, it'll make the code for a great deal of operations a bit more complicated, but would the performance benefit be worth it? Are there any reasons not to implement an ArrayList in this way?

[JosAH]

The current ArrayList implementation guarantees the random access is O(1); I don't think a doubly linked list of 'chunks' can do that ...

kind regards,

Jos

[pifrely]

Well, no, probably not. But what of the ArrayList of chunks?