Trinithis
12-31-2007, 06:52 PM
Would anyone know of an array-like data structure that has the following properties that exectute at constant time?
Lookup
Insertion at the front
Insertion at the back
If this is not possible, I need a structure with random access and fast insertion to at least one of the ends.
For those who want to know, I'm making a Befunge (http://en.wikipedia.org/wiki/Befunge) interpreter in Java using Funge-98 (http://quadium.net/funge/spec98.html) specification.
Another possibility I had in mind is a list of arrays. Not a 2d array, but perhaps like a ArrayList or LinkedList containing arrays of size X. Basically it would function as a linear array with the benefit of only rewriting "sub"array references rather than the whole deal when expanding, while at the same time being more or less random access. Perhaps this only seems good at a surface level. Either I'll test it or take someone's word.
Lookup
Insertion at the front
Insertion at the back
If this is not possible, I need a structure with random access and fast insertion to at least one of the ends.
For those who want to know, I'm making a Befunge (http://en.wikipedia.org/wiki/Befunge) interpreter in Java using Funge-98 (http://quadium.net/funge/spec98.html) specification.
Another possibility I had in mind is a list of arrays. Not a 2d array, but perhaps like a ArrayList or LinkedList containing arrays of size X. Basically it would function as a linear array with the benefit of only rewriting "sub"array references rather than the whole deal when expanding, while at the same time being more or less random access. Perhaps this only seems good at a surface level. Either I'll test it or take someone's word.