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

Latest run results:

Run details: (Test run date: 2 months ago)

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

Browser/OS: Firefox Mobile 135 on Android

View result in a separate tab

Test name	Executions per second
Double Array	16.7 Ops/sec
Linked List	296.6 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):

LLMs can make mistakes. Check important info.

I'll break down the explanation into manageable chunks.

**Benchmark Overview**

The benchmark is designed to compare the performance of two queue data structures: a linked list queue and a double array queue. The test aims to evaluate which implementation performs better under different scenarios.

**Script Preparation Code**

The script preparation code consists of two main functions:

1. `createLinkedListQueue()`: This function creates a linked list queue implementation with methods for enqueueing, dequeueing, and checking the size.
2. `createDoubleArrayQueue()`: This function creates a double array queue implementation with methods for enqueueing, dequeueing, and checking if the queue is empty.

**Benchmark Definition**

The benchmark definition consists of two test cases:

1. **"Double Array"`**: This test case executes a loop that dequeues an element from the double array queue `1000000` times.
2. **"Linked List"`**: This test case executes a loop that dequeues an element from the linked list queue `1000000` times.

**Library and Framework**

The benchmark uses two libraries:

1. None (custom implementation of queue data structures)
2. None (custom implementation of reverse array method)

**Special JS Feature or Syntax**

There are no special JavaScript features or syntax used in this benchmark.

**Pros and Cons of Approaches**

Here's a brief summary of the pros and cons of each approach:

1. **Linked List Queue**:
	* Pros: Can efficiently handle dynamic growth and contraction, allows for efficient insertion and deletion at any position.
	* Cons: May incur additional overhead due to the need to traverse the list to find the next node.
2. **Double Array Queue**:
	* Pros: Provides a fixed-size array, which can simplify implementation and reduce memory allocation overhead.
	* Cons: Inefficient for dynamic growth and contraction, as it requires reversing the entire array.

**Other Considerations**

When choosing between these two approaches, consider the following factors:

1. **Performance**: Linked list queues are generally faster for large datasets, while double array queues are more suitable for smaller datasets or when memory allocation is a concern.
2. **Memory Usage**: Double array queues use more memory due to the fixed-size array, which can be beneficial if memory efficiency is critical.
3. **Implementation Complexity**: Linked list queues require more complex implementation, as they need to handle insertion and deletion at any position.

**Alternatives**

Other queue data structures that could be used for this benchmark include:

1. Array-based queue
2. Stack-based queue
3. Hash table-based queue

However, the linked list queue and double array queue implementations provide a good trade-off between performance, memory usage, and implementation complexity.

Keep in mind that the choice of queue data structure ultimately depends on the specific requirements and constraints of your application or use case.

Related benchmarks:

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: 8 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

Autogenerated LLM Summary (model llama3.2:3b, generated 6 months ago):