A List implementation backed by multiple small arrays rather than the traditional single large array.
martinrb at google.com
Tue Mar 30 15:20:22 PDT 2010
On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern <kevin.l.stern at gmail.com> wrote:
> Hi Martin,
> Thanks much for your feedback. The first approach that comes to mind to
> implement O(1) time front as well as rear insertion is to create a cyclic
> list structure with a front/rear pointer - to insert at the front requires
> decrementing the front pointer (modulo the size) and to insert at the rear
> requires incrementing the rear pointer (modulo the size). We need to resize
> when the two pointers bump into each other. Could you explain more about
> your suggestion of introducing an arraylet that is shared by the front and
> the rear?
It was a half-baked idea - I don't know if there's a way to turn it into
something useful. I was thinking of the ArrayDeque implementation,
where all the elements live in a single array.
> It's not clear to me how that would help and/or be a better
> approach than the cyclic list. Anyhow, the paper that you reference,
> "Resizable arrays in optimal time and space", gives a deque so if we take
> that approach then the deque is specified.
Technically, ArrayList also supports the Deque operations -
just not efficiently.
More information about the core-libs-dev