How to: Implement a Queue Data Structure using Linked List in Typescript (Code below!)

Why use a Queue?

Other applications of the Queue structure:

1. First come first serve scheduling in operating systems.

2. When transferring data asynchronously → like in pipes or file IO.

3. Semaphores

4. Queues in routers/switches

5. Music playlist in Spotify

Different Types of Queue in Data Structures:

Simple Queue

Circular Queue

Priority Queue

Double-ended Queue (also called Deque)

Queue using Linked List:

iruka/src/data-structures at master · jeffzh4ng/iruka

A collection of classical data structures ⛩ and algorithms 🏃‍♂️ implemented in Typescript with video lectures 📹. - iruka/src/data-structures at master · jeffzh4ng/iruka

https://github.com/jeffzh4ng/iruka/tree/master/src/data-structures

utils.ts

/**
 * Function signature for checking equality
 */
 export interface EqualsFunction<T> {
    (a: T, b: T): boolean
  }
  
  /**
   * Function signature for comparing
   * > 0 => a is larger than b
   * = 0 => a equals b
   * < 0 => a is smaller than b
   */
  export interface CompareFunction<T> {
    (a: T, b: T): number
  }
  
  /**
   * Default function to test equality.
   * @function
   */
  export const defaultEquals = <T>(a: T, b: T): boolean => {
    return a === b
  }
  
  export const VALUE_DOES_NOT_EXIST_ERROR = 'Value does not exist.'
  
  /**
   * Default function to compare element order.
   * @function
   */
  export function defaultCompare<T>(a: T, b: T): number {
    if (a < b) {
      return -1
    } else if (a === b) {
      return 0
    } else {
      return 1
    }
  }

LinkedListNode.ts

class LinkedListNode<T> {
  val: T
  next: LinkedListNode<T> | null
  prev: LinkedListNode<T> | null

  constructor(val: T) {
    this.val = val
    this.next = null
    this.prev = null
  }
}

export default LinkedListNode

LinkedList.ts

import LinkedListNode from './LinkedListNode'
import * as utils from '../utils'

interface List<T> {
  head: LinkedListNode<T>
  tail: LinkedListNode<T>
  size: number
}

class LinkedList<T> implements Iterable<T> {
  private list: List<T> | undefined
  private equalsF: utils.EqualsFunction<T> = utils.defaultEquals

  /**
   * Creates a LinkedList - O(1)
   * @param equalsFunction equal function for for non-primitive values.
   */
  constructor(equalsFunction?: utils.EqualsFunction<T>) {
    this.list = undefined

    if (equalsFunction) this.equalsF = equalsFunction
  }

  /*****************************************************************************
                                  INSPECTION
  *****************************************************************************/
  /**
   * Returns size - O(1)
   * @return {number}
   */
  size(): number {
    if (this.list) return this.list.size

    return 0
  }
  /**
   * Returns true if inked list is empty, false otherwise - O(1)
   * @return {number}
   */
  isEmpty(): boolean {
    return !this.list
  }

  /*****************************************************************************
                                  INSERTION
  *****************************************************************************/
  /**
   * Adds node to the head of the linked list - O(1)
   * @param {T} val - value to add to list
   * @return {void}
   */
  addFront(val: T): boolean {
    const newNode = new LinkedListNode(val)

    if (this.list) {
      // link old head backwards
      this.list.head.prev = newNode

      // link new head forwards
      newNode.next = this.list.head

      this.list.head = newNode
      this.list.size += 1
    } else {
      this.list = {
        head: newNode,
        tail: newNode,
        size: 1,
      }
    }

    return true
  }
  /**
   * Adds node to the tail of the linked list - O(1)
   * @param {T} - value to add to list
   * @return {void}
   */
  addBack(val: T): boolean {
    const newNode = new LinkedListNode(val)

    if (this.list) {
      // link old tail forwards
      this.list.tail.next = newNode

      // link new tail backwards
      newNode.prev = this.list.tail

      this.list.tail = newNode
      this.list.size += 1
    } else {
      this.list = {
        head: newNode,
        tail: newNode,
        size: 1,
      }
    }

    return true
  }
  /**
   * Adds a node at specified index - O(n)
   * @param {number} i - index
   * @param {T} val - value to add to list
   * @return {void}
   */
  addAt(i: number, val: T): boolean {
    if (i === 0) {
      return this.addFront(val)
    }

    if (i === this.size()) {
      return this.addBack(val)
    }

    if (i < 0 || i >= this.size() || !this.list) return false

    let cur = this.list.head
    // traverse to index
    for (let j = 0; j < i - 1; j++) {
      cur = cur.next! // eslint-disable-line
    }

    const newNode = new LinkedListNode(val)

    // link next node
    cur.next!.prev = newNode // eslint-disable-line
    newNode.next = cur.next

    // link prev node
    newNode.prev = cur
    cur.next = newNode

    this.list.size += 1

    return true
  }

  /*****************************************************************************
                                  ACCESSING
  *****************************************************************************/
  /**
   * Gets the value of head - O(1)
   * @returns {T} value of head
   */
  peekFront(): T | null {
    if (!this.list) return null
    return this.list.head.val
  }
  /**
   * Gets the value of tail - O(1)
   * @returns {T} value of tail
   */
  peekBack(): T | null {
    if (!this.list) return null
    return this.list.tail.val
  }
  /**
   * Gets the element at index i - O(n)
   * @param {number} i - index of element
   * @returns {T} value of element at index i
   */
  get(i: number): T | null {
    if (i < 0 || i >= this.size() || !this.list) {
      return null
    }

    let j = 0
    let cur = this.list.head
    while (j < i) {
      cur = cur.next! // eslint-disable-line
      j++
    }

    return cur.val;
  }
/*****************************************************************************
                                  ALTERING
*****************************************************************************/
  /**
   * Sets the value of the current node i - O(n)
   * @returns {T} value of current node
   */
   set(i: number, value: T): void {

    if (!this.list) return;

    if (i < 0 || i >= this.list.size) return;

    let j = 0
    let cur = this.list.head

    // traverse to node to be deleted
    while (j < i) {
      cur = cur.next! // eslint-disable-line
      j += 1
    }
    cur.val = value;
  }
  /*****************************************************************************
                                  SEARCHING
  *****************************************************************************/
  /**
   * Removes the first occurrence of the specified item in the linked list.
   * @param {T} value - value to search for
   * @return {number} the index of the first occurence of the element, and -1
   * if the element does not exist.
   */
  indexOf(value: T): number {
    // list is empty
    if (!this.list) return -1

    let i = 0
    let cur = this.list.head

    while (!this.equalsF(cur.val, value)) {
      // cur.next === null means we reached end of list without finding element
      if (!cur.next) return -1

      cur = cur.next
      i += 1
    }

    return i
  }
   /**
   * Returns the first occurrence of the specified key and value in the linked list.
   * @param {T} value - value to search for
   * @return {number} the index of the first occurence of the element, and -1
   * if the element does not exist.
   */
    indexOfKey(key: string, value: string): number {
        // list is empty
        if (!this.list) return -1
    
        let i = 0
        let cur = this.list.head
    
        while(cur.next){
            const idx =  Object.keys(cur.val).indexOf(key);
            if(idx > -1 && Object.values(cur.val)[idx] === value){
                return i;
            }
        cur = cur.next;
        i += 1;
        }
        return -1;
      }
  /**
   * Checks if value is in linked list.
   * @param {T} value  - value to search for
   * @returns {boolean}
   */
  contains(value: T): boolean {
    const index = this.indexOf(value)

    return index !== -1
  }

  /*****************************************************************************
                                  DELETION
  *****************************************************************************/
  /**
   * Removes head - O(1)
   * @return {T} - value of removed head
   */
  removeFront(): T | null {
    if (!this.list) return null

    // extract val of head so we can return it later
    const val = this.list.head.val

    if (this.list.head.next) {
      // newHead.prev = null
      this.list.head.next.prev = null

      // move head pointer forwards
      this.list.head = this.list.head.next

      this.list.size -= 1
    } else {
      // list is size 1, clear the list
      this.list = undefined
    }

    return val
  }
  /**
   * Removes tail - O(1)
   * @return {T} - value of removed head
   */
  removeBack(): T | null {
    if (!this.list) return null

    // extract the val of tail so we can return it later
    const val = this.list.tail.val

    if (this.list.tail.prev) {
      // newTail.next = null
      this.list.tail.prev.next = null

      // move tail pointer backwards
      this.list.tail = this.list.tail.prev

      this.list.size -= 1
    } else {
      this.list = undefined
    }

    return val
  }
  /**
   * Removes first occurence of node with specified value. Returns true if
   * removal was successful, and false otherwise. - O(n)
   * @param {T} val - value to remove
   * @returns {T} - value of removed node
   */
  remove(val: T): T | null {
    const index = this.indexOf(val) // O(n)
    if (index === -1) return null

    return this.removeAt(index) // O(n)
  }
  /**
   * Removes node at specified index- O(n)
   * @param {number} i - index to remove
   * @return {T} - value of removed node
   */
  removeAt(i: number): T | null {
    if (!this.list) return null

    if (i === 0) {
      return this.removeFront()
    } else if (i === this.size() - 1) {
      return this.removeBack()
    }

    if (i < 0 || i >= this.list.size) return null

    let j = 0
    let cur = this.list.head

    // traverse to node to be deleted
    while (j < i) {
      cur = cur.next! // eslint-disable-line
      j += 1
    }

    // delete node
    cur.prev!.next = cur.next // eslint-disable-line
    cur.next!.prev = cur.prev // eslint-disable-line

    this.list.size -= 1

    return cur.val
  }
  /**
   * Deletes all nodes - O(1)
   */
  clear(): void {
    this.list = undefined
  }

  /*****************************************************************************
                                  HELPERS
  *****************************************************************************/
  /**
   * Appends values from an array to list - O(k)
   */
  fromArray(A: T[]): LinkedList<T> {
    for (const a of A) {
      this.addBack(a)
    }

    return this
  }

  *[Symbol.iterator](): Iterator<T> {
    if (!this.list) return

    let cur: LinkedListNode<T> | null

    for (cur = this.list.head; cur != null; cur = cur.next) {
      yield cur.val
    }
  }
}

export default LinkedList

Queue.ts

import LinkedList from "../linkedList/LinkedList";
import * as utils from '../utils';

class Queue<T> implements Iterable<T> {
    private list: LinkedList<T>
  
    constructor(equalsFunction?: utils.EqualsFunction<T>) {
      if (equalsFunction) this.list = new LinkedList(equalsFunction)
      else this.list = new LinkedList()
    }
  
    /*****************************************************************************
                                    INSPECTION
    *****************************************************************************/
    /**
     * Returns size of queue - O(1)
     */
    size(): number {
      return this.list.size()
    }
    /**
     * Returns true if queue is empty, false otherwise - O(1)
     */
    isEmpty(): boolean {
      return this.list.isEmpty()
    }
    /**
     * Deletes all elements in queue - O(1)
     */
    clear(): void {
      this.list.clear()
    }
  
    /*****************************************************************************
                                    INSERTION/DELETION
    *****************************************************************************/
    /**
     * Enqueues element into queue - O(1)
     * @param {T} element - element to be enqueued
     */
    enqueue(element: T): void {
      this.list.addBack(element)
    }
    /**
     * Dequeues element from queue - O(1)
     * @returns {T}
     */
    dequeue(): T | null {
      if (this.isEmpty()) return null
      return this.list.removeFront()
    }
  
    /*****************************************************************************
                                    ACCESSING
    *****************************************************************************/
    /**
     * Peeks at the element at the front of the queue - O(1)
     * @returns {T} - Frontmost element
     */
    peekFront(): T | null {
      if (this.isEmpty()) return null
      return this.list.peekBack()
    }
    /**
     * Peeks at the element at the back of the queue - O(1)
     * @returns {T} - Backmost element
     */
    peekBack(): T | null {
      if (this.isEmpty()) return null
      return this.list.peekFront()
    }
  
    /**
   * Gets the element at index i - O(n)
   * @param {number} i - index of element
   * @returns {T} value of element at index i
   */
  get(i: number): T | null {
    if (i < 0 || i >= this.size() || !this.list) {
      return null
    }
    return this.list.get(i);
  }
  /*****************************************************************************
                                  ALTERING
*****************************************************************************/
  /**
   * Sets the value of the current node i - O(n)
   * @returns {T} value of current node
   */
   set(i: number, value: T): void {

    if (!this.list) return;

    if (i < 0 || i >= this.size()) return;

    this.list.set(i, value);
  }
    /*****************************************************************************
                                    SEARCHING
    *****************************************************************************/
    /**
     * Checks if value is in queue - O(n)
     * @param {T} element  - element to search for
     * @returns {boolean}
     */
    contains(element: T): boolean {
      return this.list.contains(element)
    }

    /**
    * Removes the first occurrence of the specified item in the linked list.
    * @param {T} value - value to search for
    * @return {number} the index of the first occurence of the element, and -1
    * if the element does not exist.
    */
  indexOf(value: T): number {
    // list is empty
    if (!this.list) return -1

    return this.list.indexOf(value)
  }

    /**
   * Returns the first occurrence of the specified item in the linked list.
   * @param {T} value - value to search for
   * @return {number} the index of the first occurence of the element, and -1
   * if the element does not exist.
   */
 indexOfKey(key: string, value: string): number {       
 // list is empty
    if (!this.list) return -1
    return this.list.indexOfRequestId(key, value);
  }
  
  /*****************************************************************************
                                  HELPERS
  *****************************************************************************/
    [Symbol.iterator](): Iterator<T> {
      return this.list[Symbol.iterator]()
    }
  }
  
  export default Queue

index.ts - test implementation

import Queue from "./queue/Queue";

const networkQueueMaxSize = 100;
const exampleObj = [];
let temp = {} as any;
temp["3"] = {requestId: "3", type: 'sans', response: "1", time: 'sans', page: "1", tabid: 'sans'};
temp["2"] = {requestId: "2", type: 'iphone'};
temp["1"] = {response: "world", requestId: "1"}

let networkLogFromWebRequest = {} as any;
//suppose, we have 5 tabs
for(let tabId=0; tabId<5; tabId++){
    if(networkLogFromWebRequest[tabId] === undefined){
      console.log("initialize queue:"+tabId);
      networkLogFromWebRequest[tabId] = new Queue();
    }
}

let x = 1;
networkLogFromWebRequest[x].enqueue(temp["1"]);
networkLogFromWebRequest[x].enqueue(temp["2"]);
const sans = { time: new Date() }
const key = 'requestId';
const value = "1";
const idx = networkLogFromWebRequest[x].indexofKey(key, value);

if (idx !== -1) {
  const newSetValue = { ...networkLogFromWebRequest[x].get(idx), ...temp["3"] };
  networkLogFromWebRequest[x].set(idx, newSetValue);
} else{
  console.log("why is it null?");
}

const networkLogs = [];

const iterateQueue = networkLogFromWebRequest[x][Symbol.iterator]();

  for (let i = 0; i < networkLogFromWebRequest[x].size(); i++) {
    networkLogs.push(iterateQueue.next().value);
  }

  console.log(networkLogs);
  
 const iterateQueue = networkLogFromWebRequest[x][Symbol.iterator]();

 for(let i=0; i<networkLogFromWebRequest[x].size(); i++){
    console.log(iterateQueue.next().value);
 }

Credits:

References: