Deque

Double-ended queue adapter over a doubly linked value list — O(1) push/pop/peek at both ends, plus Python-style rotate().

See also: RingBuffer — the array-backed sibling with the same API; faster on raw throughput, while the list-backed deque keeps stable node identity.

Legend for tables

• API

  • value - the value to be stored in the deque
  • values - an iterable that provides values
  • iterator - an Iterator instance or an object with an iterator/iterable protocol

• Complexity

  • O - complexity of an operation
  • O(1) - constant time
  • O(n) - linear time proportional to the deque size
  • O(k) - linear time proportional to the argument size

deque.js

Deque adapter; defaults to ValueList:

import Deque from 'list-toolkit/deque.js';

const deque = new Deque();
deque.pushBack(2).pushBack(3).pushFront(1); // 1, 2, 3
deque.rotate(); // 3, 1, 2

Class Deque

Methods:

Member	Return type	Description	O
constructor(underlyingList = new ValueList())	this	constructs a new Deque	O(k)
isEmpty	boolean	checks if the deque is empty	O(1)
size	number	the deque's size	O(1)
list	list	the underlying list	O(1)
front	value or undefined	the first element	O(1)
back	value or undefined	the last element	O(1)
peekFront()	value or undefined	the first element	O(1)
peekBack()	value or undefined	the last element	O(1)
pushFront(value)	this	add an element at the front	O(1)
unshift(value)	this	an alias for pushFront(value)	O(1)
addFront(value)	this	an alias for pushFront(value)	O(1)
pushBack(value)	this	add an element at the back	O(1)
push(value)	this	an alias for pushBack(value)	O(1)
add(value)	this	an alias for pushBack(value)	O(1)
addBack(value)	this	an alias for pushBack(value)	O(1)
popFront()	value or undefined	remove and return the first element	O(1)
shift()	value or undefined	an alias for popFront()	O(1)
removeFront()	value or undefined	an alias for popFront()	O(1)
popBack()	value or undefined	remove and return the last element	O(1)
pop()	value or undefined	an alias for popBack()	O(1)
removeBack()	value or undefined	an alias for popBack()	O(1)
pushValuesFront(values)	this	add values at the front (they end up reversed)	O(k)
pushValuesBack(values)	this	add values at the back	O(k)
rotate(n = 1)	this	rotate: back → front for positive n, front → back for negative	O(min(k, n−k))
clear()	this	remove all elements from the deque	O(1)
[Symbol.iterator]()	iterator	return the default iterator starting from the first element	O(1)
getReverseIterator()	iterator or undefined	return the reverse iterator starting from the last element	O(1)

Static members:

Member	Return type	Description	O
from(values, underlyingList?)	Deque	create a deque from an iterable	O(k)

The constructor accepts a list instance or a list class — new Deque(myList) adopts, new Deque(ValueList) instantiates. The list must be DLL-based (both ends need O(1)): ValueList qualifies, ValueSList does not (popBack is O(n) on an SLL). A non-empty list triggers O(n) size initialization.

rotate(n) follows Python's deque.rotate semantics: rotate(1) moves the last element to the front. It rotates in the cheaper direction, so the cost is at most size / 2 node moves.

The Array-parity aliases (push/pop at the back, unshift/shift at the front) make the deque a drop-in for array-based queue idioms without the O(n) Array.prototype.shift.

Alias families (zero-cost, not thunks): pushFront/unshift/addFront, pushBack/push/add/addBack, popFront/shift/removeFront, popBack/pop/removeBack.

Exports

Deque is the default export.