Last active
May 20, 2025 22:24
-
-
Save midhunkrishna/4896bdd3e07e7e1bbbb3e8cd8d7163b5 to your computer and use it in GitHub Desktop.
A typescript Double Ended Queue implementation using doubly linked list.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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