Indexing (maintaining indices) in an array makes Array.prototype.shift and Array.prototype.unshift O(N) instead of O(1).
However, if we just want to use pop() / push() / shift() and unshift() and never use indices for lookup, is there a way to implement a JavaScript array that omits indexing?
I can't think of a way to do it. The only way I can think of doing it would be with arrays, and only using pop() / push() (since those are O(1)) ... but even with multiple arrays, not sure if it's possible.
Looking to do this w/o a linked-list if possible. I implemented a solution to this with a doubly linked list, but wondering if it's possible to do this w/o a linked-list.
End goal: trying to create a FIFO queue where all operations are in constant time, without using a linked-list.
How about an ES2015 Map that you index with integers?
Let's call the map myFIFOMap.
You keep a first and last integer member as part of your FIFO class. Start them both at zero.
Every time you want to push() into your FIFO queue, you call myFIFOMap.set(++last,item). And pop() looks something like:
const item = myFIFOMap.get(first);
myFIFOMap.delete(first++);
return item;
Should be O(1) to push or pop.
Don't forget to check for boundary conditions (e.g., don't let them pop() when first===last).
Given that JavaScript actually uses double precision floating point, you should be able to run ~2^53 objects through your FIFO before you have problems with the integer precision. So if you run 10,000 items through your FIFO per second, that should be good for around 28,000 years of run time.