A typescript Double Ended Queue implementation using doubly linked list.

deque.ts

/**
 * 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;
  }
}