Data Structures​

Linked List

A Linked list is a group of nodes which together represent a sequence. linked list contains 2 things.

1. The actual data being stored
2. The next location or pointer to the next node

head['data', pointer(1)] -> 1['data', pointer(2)] -> tail['data', null]

Code:

function linkedList() {
  let size = 0; //size of our linked list
  let head = null; // pointer to next location
  
  // create new node
  const Node = function(element) {
    this.element = element;
    this.next = null;
  }

  this.size = (() => {
    return size;
  });

  this.head = (() => {
    return head;
  });

  this.add = ((element) => {
    const node = new Node(element);

    if (head === null) {
      head = node;
    } else {
      let currentNode = head;

      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }
    size++;
  });

  this.remove = ((element) => {
    let currentNode = head;
    let previousNode;

    if (currentNode.element === element) {
      head = currentNode.next;
    } else {
      while (currentNode.element !== element && currentNode.next) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    size--;
  });

  this.empty = (() => {
    return size === 0;
  });

  this.indexOf = ((element) => {
    let currentNode = head;
    let index = -1;
    while (currentNode) {
      index++;
      if (currentNode.element === element) return index;
      currentNode = currentNode.next;
    }
    return -1;
  });

  this.elementOf = ((index) => {
    let currentNode = head;
    let count = 0;
    while (index > count) {
      currentNode = currentNode.next;
      count++;
    }
    return currentNode.element;
  });
}

Stacks

A stack is a basic data structure where things can only be added or removed from the top. First in Last out approach and this is how recursion fundamentally works.
Methods:

1. Push -> Insert onto the stack
2. Pop -> Remove from the stack
3. Pip -> View the stack

function stack() {
  this.count = 0;
  this.data = {};

  this.push = function(value) {
    this.data[this.count] = value;
    this.count++;
  };
  this.pop = function() {
    if (this.count === 0) return undefined;
    this.count--;
    const result = this.data[this.count];
    delete this.data[this.count];
    return result;
  };
  this.pip = function() {
    return this.data[this.count-1];
  };
  this.length = function() {
    return this.count;
  };
}

Queue

A Queue is essentially a waiting line. First in, First out approach.
Methods:

1. Enqueue -> insert to the queue
2. Dequeue -> remove from the queue

function queue(){
  const que = [];

  this.enqueue = ((element) => {
    que.push(element);
  });

  this.dequeue = (() => {
    return que.shift();
  });

  this.length = (() => {
    return que.length;
  });
}

Sets

The set data structure stores values without any particular order with no repeated values.
Methods:

1. Add
2. Remove
3. Union -> Combines all elements from 2 different sets -> returns new deduped set.
4. Intersection -> Compares 2 or more sets and returns a new set with items that are in all sets.
5. Difference -> Returns new set with items that are not in a different set.
6. Subset -> returns a boolean if all items in Set A are in Set B

Maps

A map is a data structure that stores data in key value pairs. Maps are sometimes referred to as dictionaries.
Methods:
Crud

function map(){
  let data = {};
  let count = 0;

  this.add = ((key, value) => {
    console.log(value);
    data[key] = value;
    count++;
  });

  this.has = ((key) => {
    return (data[key] !== undefined);
  });

  this.get = ((key) => {
    return data[key];
  });
}

Hash Table

A hash table is a map or array data structure that uses a hash function to locate the index of the requested data in an array.
String -> hashFunction(string) -> Array(int). See more on hashe tables here

Binary Search Tree

A tree is a data structure consisting of nodes. Each tree has a root node and each child has 0 or more children. Each child also has 0 or more children. See more on binary trees here

Trie

A prefixed tree is a kind of search tree. Trie stores data in steps where each step is a node in the tree. Trie are most commonly used to store words for quick lookup, such as auto-complete or auto-correct features we all love and hate. Each node contains 2 things.

1. The data like the letter "A"
2. Boolean value signaling a stopping point like the end of a word

The Root of the trie is almost always blank and works from top down.

Binary Heap

Tree data structure, every node at most has 2 children and is filled from left to right. Read more about how a heap can be used to sort data here