Benchmark: Linked List Queue vs Double Array Queue vs Queue with Map

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
		}
	}
}

class Queue {
    #queue = new Map()
    #head = 0
    #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
    }

    size() {
        return this.#tail - this.#head
    }
}

var doubleQ = createDoubleArrayQueue()
var linkedListQ = createLinkedListQueue()
var queue = new Queue()
var queueSize = 1000

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++) { linkedListQ.dequeue() }
LinkedList deque
for(let i = 0; i < queueSize; i++) { linkedListQ.dequeue() }
Queue deque
for(let i = 0; i < queueSize; i++) { queue.dequeue() }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Double Array enque
Linked List enque
Queue enqeue
Array deque
LinkedList deque
Queue deque

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one month ago):

LLMs can make mistakes. Check important info.

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_13_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/114.0.0.0 YaBrowser/23.7.0.2564 Yowser/2.5 Safari/537.36

Browser/OS: Yandex Browser 23 on Mac OS X 10.13.6

View result in a separate tab

Test name	Executions per second
Double Array enque	5952.3 Ops/sec
Linked List enque	2640.0 Ops/sec
Queue enqeue	2036.1 Ops/sec
Array deque	3725.6 Ops/sec
LinkedList deque	1898.3 Ops/sec
Queue deque	3530.6 Ops/sec

Related benchmarks:

Linked List Queue vs Double Array Queue vs Queue with Map (version: 0)

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

Comparing performance of: Double Array enque vs Linked List enque vs Queue enqeue vs Array deque vs LinkedList deque vs Queue deque

Created: one year ago by: Guest

Jump to the latest result

Double Array enque

Linked List enque

Queue enqeue

Array deque

LinkedList deque

Queue deque

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one month ago):