MV's blog

Deques

A deque is a data structure that stores a collection of values T. It is a generalization of the stack and queue data structures that supports adding and removing items from either the front or the back of the data structure.

Sample typescript implementation that uses a doubly linked list for storing the values. For linked lists refer here.

class ListNode<T> {
  value: T;
  prev: ListNode<T>;
  next: ListNode<T>;
}

export class Deque<T> {
  private first: ListNode<T> = null;
  private last: ListNode<T> = null;
  private count: number = 0;

  public addFirst(value: T): void {
    if (value == null) throw new Error('Invalid value');

    const node = new ListNode<T>();
    node.value = value;
    node.next = this.first;
    node.prev = null;

    if (this.isEmpty()) {
      this.last = node;
    } else {
      this.first.prev = node;
    }

    this.first = node;
    this.count++;
  }

  public addLast(value: T): void {
    if (value == null) throw new Error('Invalid value');

    const node = new ListNode<T>();
    node.value = value;
    node.next = null;
    node.prev = this.last;

    if (this.isEmpty()) {
      this.first = node;
    } else {
      this.last.next = node;
    }

    this.last = node;
    this.count++;
  }

  public removeFirst(): T {
    if (this.isEmpty()) throw new Error('Invalid operation');

    const value = this.first.value;

    this.first = this.first.next;
    this.count--;

    if (this.isEmpty()) {
      this.last = this.first;
    } else {
      this.first.prev = null;
    }

    return value;
  }

  public removeLast(): T {
    if (this.isEmpty()) throw new Error('Invalid operation');

    const value = this.last.value;

    this.last = this.last.prev;
    this.count--;

    if (this.isEmpty()) {
      this.first = null;
    } else {
      this.last.next = null;
    }

    return value;
  }

  public isEmpty(): boolean {
    return this.count === 0;
  }

  public size(): number {
    return this.count;
  }
}

Alternatively it can be implemented with an array, either a predefined one or with resizing; depending on the use case.

The time cost for the addFirst(), addLast(), removeFirst() and removeLast() operations is O(1).