Benchmark: Linked List Queue vs Double Array Queue

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() }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Double Array
Linked List

Fastest: N/A

Slowest: N/A

ⓘ Get performance results from real users on your website with Request Metrics.

Website Performance Monitoring by Request Metrics

Latest run results:

Run details: (Test run date: 21 days ago)

User agent: Mozilla/5.0 (Android 14; Mobile; rv:124.0) Gecko/124.0 Firefox/124.0

Browser/OS: Firefox Mobile 124 on Android

View result in a separate tab

Test name	Executions per second
Double Array	25.5 Ops/sec
Linked List	79.2 Ops/sec

Linked List Queue vs Double Array Queue (version: 5)

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

Comparing performance of: Double Array vs Linked List

Created: 7 years ago by: Registered User

Jump to the latest result

Double Array

Linked List

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A