We should provide a generalization of ArrayDeque that also implements List.
(Also, perhaps ArrayDeque should be retrofitted to implement List)

It is known that one can implement resizable arrays with these performance characteristics:
- O(1) insert and remove from head
- O(1) insert and remove from tail
- O(1) random access to read or write element i
- O(sqrt(N)) wasted space
- O(sqrt(N)) insert and remove from the middle

The basic idea is to use ArrayDeques as the fundamental unit of storage, but if the
size grows too large, expand to an array of ArrayDeques, and perhaps recursively
to a tree of such arrays.

Such a data structure won't have the best performance for any particular operation,
but it won't have pathologically bad performance for any of the targeted operations
when the size is large, a disease which afflicts all current collections.

This data structure is *not* designed for multi-threaded use; it must be
wrapped in a synchronizedFoo

References:

http://en.wikipedia.org/wiki/Dynamic_array
http://www.cs.jhu.edu/~goodrich/cgc/pubs/index.html # Tiered vectors
http://www.cs.brown.edu/cgc/jdsl/papers/tiered-vector.pdf
http://jhu.edu/~goodrich/cgc/pubs/wads99.ps
http://www.eecs.umich.edu/~bchandra/publications/oopsla01.pdf # Race free collections
http://lampwww.epfl.ch/papers/techlists.pdf # Vlists
http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf # RAOTS
http://www.cphstl.dk/Report/Deque/cphstl-report-2001-7.ps # space-efficient deques
http://www.cphstl.dk/Report/Deque-first-attempt/cphstl-report-2001-4.pdf
Posted Date : 2006-01-04 19:20:09.0

N/A

A fine idea.  A good project for a master's thesis?
Posted Date : 2006-01-04 19:20:09.0

Even without the array of arraydeques, if ArrayDeque implements List from now on, it would be a incredibly good replacement for ArrayList, since adding and removing from the head would cost O(1).