On Tue, Mar 30, 2010 at 04:25, Kevin L. Stern <[email protected]> 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.
