Data Structures in JavaScript

This is a post that briefly describes common computer science data structures in JavaScript.

Stack

A stack in JavaScript is an array

const stack = []
stack.push(2) // [2]
stack.unshift(1,4) // [1,4,2]
stack.pop() // [1,4]
stack.shift() // [4]

You can use a stack when dealing with Queues, either a FIFO or LIFO.

Linked List

class LinkedListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
// create the first node
const head = new LinkedListNode(2);
// add a second node
head.next = new LinkedListNode(4);
// add a third node
head.next.next = new LinkedListNode(5);

A linked list is used to point one part of memory to the next. This can be used for instance in dynamic memory allocation by the operating system.

Graph

// create a graph class
class Graph {
  constructor(noOfVertices) {
    this.noOfVertices = noOfVertices;
    this.AdjList = new Map();
  }
  addVertex(vertex) {
    this.AdjList.set(vertex, []);
  }
  addEdge(source, destination) {
    this.AdjList.get(source).push(destination);
    this.AdjList.get(destination).push(source);
  } 
  printGraph() {
    const keys = this.AdjList.keys();
    // iterate over the vertices
    for (const key of keys) {
      const values = this.AdjList.get(i);
      var conc = "";
      // iterate over the adjacency list
      // concatenate the values into a string
      for (const j of get_values) {
        conc += j + " ";
      }
      // print the vertex and its adjacency list
      console.log(i + " -> " + conc);
    }
  } 
  breathFirstSearch(vertex) {
    const visited = [];
    for (var i = 0; i < this.noOfVertices; i++) {
      visited[i] = false;
    }
    const q = new Queue();
    visited[startingNode] = true;
    q.enqueue(startingNode);
    // loop until queue is element
    while (!q.isEmpty()) {
      const getQueueElement = q.dequeue();
      console.log(getQueueElement);
      // get the adjacent list for current vertex
      var list = this.AdjList.get(getQueueElement);
      // loop through the list and add the element to the
      // queue if it is not processed yet
      for (const i in list) {
        const neighbor = list[i];
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          q.enqueue(neighbor);
        }
      }
    }
  } 
  depthFirstSearch(vertex) {
    const visited = [];
    for (const i = 0; i < this.noOfVertices; i++) {
      visited[i] = false;
    }
    this.DFSUtil(startingNode, visited);
  }
  DFSUtil(vert, visited) {
    visited[vert] = true;
    const neighbours = this.AdjList.get(vert);
    for (const i in neighbours) {
      const element = neighbours[i];
      if (!visited[element]) {
        this.DFSUtil(element, visited);
      }
    }
  } 
}

Share this on:

Edit this page on GitHub