Data Structures in JS

Data Structures are a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently. Here we are going to explore different types of data structures by implementing them in JS, use comments to explore more about each DS.

export default class Data {
  getArray (length) {
    /* an array data structure, or simply an array, is a data structure consisting 
    of a collection of elements, each identified by at least one array index or key. 
    An array is stored such that the position of each element can be computed from its 
    index tuple by a mathematical formula. */

    let arr = new Array(length)
    return arr
  }

  /* a linked list is a linear collection of data elements whose order is not given 
  by their physical placement in memory. Instead, each element points to the next. 
  It is a data structure consisting of a collection of nodes which together represent 
  a sequence. */

  getLinkedList (data) {
    let list = new LinkedList()

    if (data.length == 1) {
      list.head = new Node(data[0])
      return list
    }


    let i = data.length - 1
    let lastNode = new Node(data[i])

    while (--i >= 0) {
      let node = new Node(data[i], lastNode)
      lastNode = node
      list.head = node
    }

    return list
  }

  /* a stack is an abstract data type that serves as a collection of elements, with 
  two principal operations: push, which adds an element to the collection, and pop, 
  which removes the most recently added element that was not yet removed */

  getStack () {
    let stack = new Stack()
    return stack
  }

  /* a queue is a collection of entities that are maintained in a sequence and 
  can be modified by the addition of entities at one end of the sequence and 
  the removal of entities from the other end of the sequence. */

  getQueue () {
    let stack = new Stack()
    return stack
  }

  /* a binary tree is a tree data structure in which each node has at most two children, 
  which are referred to as the left child and the right child. */

  getTree () {
    let binaryTree = new BinarySearchTree()
    return binaryTree
  }

  /* a heap is a specialized tree-based data structure which is essentially an almost 
  complete tree that satisfies the heap property */

  /* A dictionary is a general-purpose data structure for storing a group of objects. 
  A dictionary has a set of keys and each key has a single associated value. 
  Different languages enforce different type restrictions on keys and values 
  in a dictionary. Dictionaries are often implemented as hash tables. */

  HashTable (obj) {
    this.length = 0
    this.items = {}

    for (let p in obj) {
      if (obj.hasOwnProperty(p)) {
        this.items[p] = obj[p]
        this.length++
      }
    }

    this.setItem = function(key, value) {
      let previous = undefined
      if (this.hasItem(key)) {
        previous = this.items[key]
      } else {
        this.length++
      }

      this.items[key] = value
      return previous
    }

    this.getItem = function(key) {
      return this.hasItem(key) ? this.items[key] : undefined
    }

    this.hasItem = function(key) {
      return this.items.hasOwnProperty(key)
    }

    this.removeItem = function(key) {
      if (this.hasItem(key)) {
        previous = this.items[key]
        this.length--
        delete this.items[key]
        return previous
      } else {
        return undefined
      }
    }

    this.keys = function() {
      let keys = []
      for (let k in this.items) {
        if (this.hasItem(k)) {
            keys.push(k)
        }
      }
      return keys
    }

    this.values = function() {
      let values = []
      for (let k in this.items) {
        if (this.hasItem(k)) {
            values.push(this.items[k])
        }
      }
      return values
    }

    this.each = function(fn) {
      for (let k in this.items) {
        if (this.hasItem(k)) {
          fn(k, this.items[k])
        }
      }
    }

    this.clear = function() {
      this.items = {}
      this.length = 0
    }
  }

  getHash () {
    return new Hash('one',[1,10,5],'two', [2], 'three',[3,30,300]);
  }

  /* a graph is an abstract data type that is meant to implement the undirected 
  graph and directed graph concepts from the field of graph theory within 
  mathematics. */

  getGraph () {
    return new Graph()
  }

  /* Matrix is a way to store data in an organized form in the form of rows and columns. 
  Matrices are usually used in computer graphics to project 3-dimensional space onto a
  2-dimensional screen. Matrices in the form of arrays are used to store data in an 
  organized form */

  getMatrix (n, m) {
    let matrix = new Array(m)

    for (let i = 0; i < matrix.length; i++) 
      matrix[i] = new Array(n)

    return matrix
  }

  /* Tensors are a type of data structure used in linear algebra, and like vectors 
  and matrices, you can calculate arithmetic operations with tensors. */

  getTensor (r, s, t) {
    return new Tensor(r, s, t)
  }
}