Run results for: Linked List Queue vs Double Array Queue

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/85.0.4183.121 Safari/537.36

Browser: Chrome 85

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: 4 years ago

Test name	Executions per second
Double Array	5.7 Ops/sec
Linked List	2.3 Ops/sec

Script Preparation code:

function createLinkedListQueue() {
	let length = 0
	let head = undefined
	let tail = undefined
	return {
		enqueue(value) {
			enqueueNode(value)
		},
		dequeue() {
			return dequeueNode()
		},
		size() {
			return length
		},
		head() {
			return head
		},
		tail() {
			return tail
		}
	}
	function enqueueNode(value) {
		const node = {
			value,
			next: undefined 
		}
		if(!head) {
			head = node
			tail = node
		}
		else {
			tail.next = node
			tail = node
		}
		length += 1	
	}
	function dequeueNode() {
		if(head) {
			const value = head.value
			head = head.next
			length -= 1
			return value
		}
		tail = undefined
		return undefined
	}
}

function createDoubleArrayQueue() {
	return {
		input: [],
		output: [],
		enqueue(element) {
			this.input.push(element)
		},
		dequeue() {
			if(this.output.length === 0) {
				this.pivot()
			}
			return this.output.pop()
		},
		pivot() {
			this.output = this.input.reverse()
			this.input = []
		},
		isEmpty() {
			return this.input.length === 0 && this.output.length === 0
		}
	}
}

var doubleQ = createDoubleArrayQueue()
var linkedListQ = createLinkedListQueue()
var queueSize = 1000000

for(let i = 0; i < queueSize; i++) {
  doubleQ.enqueue('testString' + i)
  linkedListQ.enqueue('testString' + i)
}

Tests:

Double Array
for(let i = 0; i < queueSize; i++) { doubleQ.dequeue() }
Linked List
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }

Run results for: Linked List Queue vs Double Array Queue

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

Double Array

Linked List