Java: `Double Ended` ArrayList Class?

[statik213]

I need to keep tack of a large amount of data (32k ~ 128k points) and after I reach a certain capacity I need to add new datapoints and discard old ones. The ArrayList class (in the JDK) can insert new elements in constant time at the top of the list (given sufficient capacity), I also would like to have it remove elements in constant time.

I could extend the ArrayList class to do this where it could leave space at the begining of its internal Array when elements are removed. Similiar to how it handles the case when things at the top of the list are removed.... But looking at the ArrayList code extending it to do this would mean rewriting the whole class as this change would affect every single method in there.

before I flesh out this code I'd like to know if there is already is an implementation like this that I can get hold of.

 

[Crusty]

I have a class that I wrote that does...
/** Removes the object at the index specified.
* Time: O(1->n)
* Space: O(1)
* @param index Index to be removed.
* @return The object removed.
*/

I don't think I really understand your question though....

like given the list:
0 | 1 | 2 | 3 | 4

and a remove(2) is performed... you want the list to become
X | 0 | 1 | 3 | 4

?

I have a class that is similar to that, but it's not always constant time for removing, best case is constand and worse case is linear.

 

[statik213]

Yeah that's more or less what I want.

I want to be able to do this:
Initial view:
... a|b|c|d|e|f ...

remove(0);
add(g);
Fina view:
... b|c|d|e|f|g ...

both ops in constant time, and every so often be hit by an O(n) op. when it runs out of space to add new elements (i.e. capacity is reached) and it has to copy the elements into a new array.

I'm talking about an array that has around 64k elements, so the way arraylist works is that it shifts the whole array left which is O(n).

I need to be able to traverse the list fast as I will be plotting parts of it in real time, and need to have random access to find values based on time (position in list - 'cos it would automatically be sorted ascending in time).

I'm not interested in adding and removing values from the middle of the list, and I'll be adding at the end of the list and removing at the bottom of the list always.

Makes sense? I suspect your Class is doing this by the way you described the remove operation as long as you haven't changed the way add works.

 

[Crusty]

Originally posted by: statik213
Yeah that's more or less what I want.

I want to be able to do this:
Initial view:
... a|b|c|d|e|f ...

remove(0);
add(g);
Fina view:
... b|c|d|e|f|g ...

both ops in constant time, and every so often be hit by an O(n) op. when it runs out of space to add new elements (i.e. capacity is reached) and it has to copy the elements into a new array.

I'm talking about an array that has around 64k elements, so the way arraylist works is that it shifts the whole array left which is O(n).

I need to be able to traverse the list fast as I will be plotting parts of it in real time, and need to have random access to find values based on time (position in list - 'cos it would automatically be sorted ascending in time).

I'm not interested in adding and removing values from the middle of the list, and I'll be adding at the end of the list and removing at the bottom of the list always.

Makes sense? I suspect your Class is doing this by the way you described the remove operation as long as you haven't changed the way add works.

ygpm

 

[statik213]

Looks good.
Thanks a lot -- should be a huge time saver!!