Skip to content

Instantly share code, notes, and snippets.

@midhunkrishna
Last active May 20, 2025 22:24
Show Gist options
  • Save midhunkrishna/4896bdd3e07e7e1bbbb3e8cd8d7163b5 to your computer and use it in GitHub Desktop.
Save midhunkrishna/4896bdd3e07e7e1bbbb3e8cd8d7163b5 to your computer and use it in GitHub Desktop.
A typescript Double Ended Queue implementation using doubly linked list.
/**
* A doubly-linked list node for Deque implementation
*/
class DequeNode<T> {
data: T | null;
next: DequeNode<T> | null;
prev: DequeNode<T> | null;
constructor(data: T | null = null) {
this.data = data;
this.next = null;
this.prev = null;
}
}
/**
* A double-ended queue (deque) implementation using doubly-linked list
* with sentinel nodes for efficient O(1) operations
*/
export class DoubleEndedQueue<T> {
private head: DequeNode<T>;
private tail: DequeNode<T>;
private _size: number;
constructor() {
this.head = new DequeNode<T>();
this.tail = new DequeNode<T>();
this.head.next = this.tail;
this.tail.prev = this.head;
this._size = 0;
}
/**
* Returns the number of elements in the deque
*/
get size(): number {
return this._size;
}
/**
* Returns true if the deque is empty, false otherwise
*/
get isEmpty(): boolean {
return this._size === 0;
}
/**
* Adds an element to the front of the deque
* @param data The element to add
*/
pushFront(data: T): void {
const newNode = new DequeNode(data);
const nextNode = this.head.next!;
newNode.prev = this.head;
newNode.next = nextNode;
this.head.next = newNode;
nextNode.prev = newNode;
this._size++;
}
/**
* Adds an element to the back of the deque
* @param data The element to add
*/
pushBack(data: T): void {
const newNode = new DequeNode(data);
const prevNode = this.tail.prev!;
newNode.next = this.tail;
newNode.prev = prevNode;
prevNode.next = newNode;
this.tail.prev = newNode;
this._size++;
}
/**
* Removes and returns the front element of the deque
* @returns The front element or undefined if empty
*/
popFront(): T | undefined {
if (this.isEmpty) return undefined;
const node = this.head.next!;
const newNext = node.next!;
this.head.next = newNext;
newNext.prev = this.head;
this._size--;
return node.data ?? undefined;
}
/**
* Removes and returns the back element of the deque
* @returns The back element or undefined if empty
*/
popBack(): T | undefined {
if (this.isEmpty) return undefined;
const node = this.tail.prev!;
const newPrev = node.prev!;
this.tail.prev = newPrev;
newPrev.next = this.tail;
this._size--;
return node.data ?? undefined;
}
/**
* Returns the front element without removing it
* @returns The front element or undefined if empty
*/
peekFront(): T | undefined {
if (this.isEmpty) return undefined;
return this.head.next?.data ?? undefined;
}
/**
* Returns the back element without removing it
* @returns The back element or undefined if empty
*/
peekBack(): T | undefined {
if (this.isEmpty) return undefined;
return this.tail.prev?.data ?? undefined;
}
/**
* Removes all elements from the deque
*/
clear(): void {
this.head.next = this.tail;
this.tail.prev = this.head;
this._size = 0;
}
/**
* Converts the deque to an array from front to back
* @returns An array containing all elements in order
*/
toArray(): T[] {
const result: T[] = [];
let current = this.head.next;
while (current && current !== this.tail) {
if (current.data !== null) {
result.push(current.data);
}
current = current.next;
}
return result;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment