Run results for: Linked List Queue vs Double Array Queue vs Queue with Map enqueue/dequeue/dequeueTail

Run details:

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:136.0) Gecko/20100101 Firefox/136.0

Browser: Firefox 136

Operating system: Windows

Device Platform: Desktop

Date tested: 27 days ago

Test name	Executions per second
Double Array enque	231.4 Ops/sec
Linked List enque	74.5 Ops/sec
Queue enqeue	22.1 Ops/sec
Array deque	434.9 Ops/sec
LinkedList deque	545.7 Ops/sec
Queue deque	41.4 Ops/sec
Array deque from Tails	309.6 Ops/sec
Linked from Tail	685.6 Ops/sec
Queue from tail	705.5 Ops/sec

Script Preparation code:

class LinkedListQueue {
  constructor() {
    this.length = 0;
    this.head = undefined;
    this.tail = undefined;
  }

  enqueue(value) {
    this.enqueueNode(value);
  }

  dequeue() {
    return this.dequeueNode();
  }

  dequeueFromTail() {
    return this.dequeueNodeFromTail();
  }

  size() {
    return this.length;
  }

  getHead() {
    return this.head;
  }

  getTail() {
    return this.tail;
  }

  enqueueNode(value) {
    const node = {
      value,
      next: undefined,
      prev: this.tail
    };

    if (!this.head) {
      this.head = node;
      this.tail = node;
    } else {
      this.tail.next = node;
      this.tail = node;
    }

    this.length += 1;
  }

  dequeueNode() {
    if (this.head) {
      const value = this.head.value;
      this.head = this.head.next;

      if (this.head) {
        this.head.prev = undefined;
      } else {
        this.tail = undefined;
      }

      this.length -= 1;
      return value;
    }

    return undefined;
  }

  dequeueNodeFromTail() {
    if (this.tail) {
      const value = this.tail.value;
      this.tail = this.tail.prev;

      if (this.tail) {
        this.tail.next = undefined;
      } else {
        this.head = undefined;
      }

      this.length -= 1;
      return value;
    }

    return undefined;
  }
}


class DoubleArrayQueue {
  constructor() {
    this.input = [];
    this.output = [];
  }

  enqueue(element) {
    this.input.push(element);
  }

  dequeue() {
    if (this.output.length === 0) {
      this.pivot();
    }
    return this.output.pop();
  }

  dequeueFromTail() {
    if (this.input.length === 0) {
      this.pivot();
    }
    return this.input.pop();
  }

  pivot() {
    this.output = this.input.reverse();
    this.input = [];
  }

  isEmpty() {
    return this.input.length === 0 && this.output.length === 0;
  }
}


class Queue {
    constructor() {
        this.queue = new Map();
        this.head = 0;
        this.tail = 0;
    }

    enqueue(item) {
        this.queue.set(this.tail, item);
        this.tail++;
    }

    dequeue() {
        if (this.head === this.tail) return;

        const value = this.queue.get(this.head);
        this.queue.delete(this.tail);
        this.head++;

        return value;
    }
            
    dequeueFromTail() {
        if (this.head === this.tail) return;
        this.tail--;
        const value = this.queue.get(this.tail);
        this.queue.delete(this.tail);
        return value;
    }

    size() {
        return this.tail - this.head;
    }
}

var doubleQ = new DoubleArrayQueue()
var linkedListQ = new LinkedListQueue()
var queue = new Queue()
var queueSize = 100000

Tests:

Double Array enque
for(let i = 0; i < queueSize; i++) { doubleQ.enqueue(i) }
Linked List enque
for(let i = 0; i < queueSize; i++) { linkedListQ.enqueue(i) }
Queue enqeue
for(let i = 0; i < queueSize; i++) { queue.enqueue(i) }
Array deque
for(let i = 0; i < queueSize; i++) { doubleQ.dequeue() }
LinkedList deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
Queue deque
for(let i = 0; i < queueSize; i++) { queue.dequeue() }
Array deque from Tails
for(let i = 0; i < queueSize; i++) { doubleQ.dequeueFromTail() }
Linked from Tail
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeueFromTail() }
Queue from tail
for(let i = 0; i < queueSize; i++) { queue.dequeueFromTail() }

Run results for: Linked List Queue vs Double Array Queue vs Queue with Map enqueue/dequeue/dequeueTail

Testing a linked list queue vs a double list queue vs Queue with Map for different performance scenarios.

Double Array enque

Linked List enque

Queue enqeue

Array deque

LinkedList deque

Queue deque

Array deque from Tails

Linked from Tail

Queue from tail