Create array structure in JavaScript that omits indexing

Question

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.

Answer 1

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.

Answer 2

If the data you are storing is primitive (string, integers, floats, or combinations of primitives), you can use a JavaScript TypedArray, cast it into an appropriate typed array view, load it with data, and then keep track of the offset(s) yourself.

In your example, pop, shift, and unshift can all implemented by incrementing/decrementing an integer index. push is more difficult, because a TypedArray is a fixed size: if the ArrayBuffer is full, the only two options are to truncate the data, or allocate a new typed array, since JS cannot store pointers.

If you are storing homogeneous objects (they have the same properties), you can save each value into a TypedArray using different views and offsets to mimic a C struct (see the MDN example), and then use a JS function to serialize/unserialize them from the TypedArray, basically converting the data from a binary representation, into a full-fledged JS object.

Answer 3

Going with @SomeCallMeTim 's answer, which I think is on the right track, I have this:

export class Queue {

  lookup = new Map<number, any>();
  first = 0;
  last = 0;
  length = 0;
  elementExists = false; // when first === last, and item exists there

  peek() {
    return this.lookup.get(this.first);
  }

  getByIndex(v: number) {
    return this.lookup.get(v);
  }

  getLength() {
    return this.length;
  }

  pop() {

    const last = this.last;

    if (this.elementExists && this.first === this.last) {
      this.length--;
      this.elementExists = false;
    }
    else if (this.last > this.first) {
      this.length--;
      this.last--;
    }

    const v = this.lookup.get(last);
    this.lookup.delete(last);
    return v;
  }

  shift() {

    const first = this.first;

    if (this.elementExists && this.first === this.last) {
      this.length--;
      this.elementExists = false;
    }
    else if (this.first < this.last) {
      this.length--;
      this.first++;
    }

    const v = this.lookup.get(first);
    this.lookup.delete(first);
    return v;
  }

  push(v: any) {

    this.length++;

    if (this.elementExists && this.first === this.last) {
      this.last++;
    }
    else if (this.first === this.last) {
      this.elementExists = true;
    }
    else {
      this.last++;
    }

    return this.lookup.set(this.last, v);

  }

  enq(v: any) {
    return this.push.apply(this, arguments);
  }

  enqueue(v: any) {
    return this.push.apply(this, arguments);
  }

  deq() {
    return this.shift.apply(this, arguments);
  }

  dequeue() {
    return this.shift.apply(this, arguments);
  }

  unshift(v: any) {

    this.length++;

    if (this.elementExists && this.first === this.last) {
      this.first--;
    }
    else if (this.first === this.last) {
      this.elementExists = true;
    }
    else {
      this.first--;
    }

    return this.lookup.set(this.first, v);
  }

  addToFront(v: any){
    return this.unshift.apply(this,arguments);
  }

  removeAll() {
    return this.clear.apply(this, arguments);
  }

  clear(): void {
    this.length = 0;
    this.elementExists = false;
    this.first = 0;
    this.last = 0;
    this.lookup.clear();
  }

}

takeaways:

1. it turns out, you can call getByIndex(), as Tim's suggestion points out.

2. Using Map is surprisingly ~10% faster than POJSO, possibly only because with a POJSO the integers need to get converted to strings for lookup.

3. The Map implementation is about 20% faster than doubly-linked list, so a doubly-linked list is not that much slower. It's probably slower mostly because we must create a container object with next/prev pointers for each item in the queue, whereas with the non-linked list implementation, we can insert primitives in the queue, etc.

4. The doubly-linked list allows us to remove/insert items from the middle of the queue in constant time; we cannot do the same with the non-linked list implementation as is.

5. All of the above are orders of magnitude more performant than a plain array when operating on an array with more than 10,000 elements or so.

I have some constant time queue implementations here: https://github.com/ORESoftware/linked-queue

Tim had a good suggestion, to make getByIndex() easier to use - we can do this:

  getByIndex(v: number) {

    if(!Number.isInteger(v)){
      throw new Error('Argument must be an integer.');
    }

    return this.lookup.get(v + this.first);
  }

that way to get the 5th element in the queue, all we need to do is:

getByIndex(4);