A List implementation backed by multiple small arrays rather than the traditional single large array.

[Martin Buchholz]

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.