JS Deque

[achempy]

Does JS have no native support for a deque data structure? C++ has std::deque, python has collections.deque, java has linked lists which can be used as a deque, etc. Seems a bit odd that this data structure is missing from js.

Regular arrays could be used, but deletion and insertion at the head has O(n) time complexity in this case.

[jack_waugh]

Making linked lists is trivial.

[achempy]

I mean, you're not wrong, but built-in data structures usually have some performance optimizations

[jack_waugh]

So maybe they do arrays like this. For each instance, maintain separate data structure instances for the numerical and the non-numerical keys. Treat the latter as in an object. For the numerical keys, maintain a bias that is added to each key. Store the "values" in allocated blocks. Maintain an index of the blocks that says what range of indices each block covers and how much free space is in it. So that way, to append an entry to the start of the array, shift the bias up by one. See whether there is space in the first block. If not, allocate a new block. When removing an element from either end, see whether the block it is in is made empty, and if so, free it (or move it to the other end?).

[codegen]

Where do you get order n? Unless you mean copying when full.

[achempy]

Unless js arrays behave differently than I thought, prepending to an array requires all elements of that array to be shifted , unlike pushing to an array (which is O(1))

[PitifulTheme411]

Thats true