[Assessment Outline: Data Structures](https://github.com/Techtonica/curriculum/tree/master/projects/data-structures-algorithms-assessment.md)

Assessment 11

## Stacks ######################################################################################################
- [X] Explain what a stack data structure is and show how it is implemented.

Stacks - last in first out (last element added will be the first removed)
      - not a built in JS data structure

EX: Collection of books, plates stacked 

Used to Undo/redo, manage function invocations, routing 
================================================
BIG O / RUNTIME: 
Priorities:
*removal & insertion - O(1) - no iteration, jump right to start

Non-Priorities
*searching & access - O(N)
================================================

IMPLEMENTATION: //following structure of SLL
//can rename shift and unshift SLL methods to be push and pop methods here (to avoid transversing)

class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    push(val){
      // create a new node with input value
        var newNode = new Node(val);
        // if there are no node in stack set first and last properties to be new nodes
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
          // if there is at least one node, store current first property on stack in variable
            var temp = this.first;
            //reset first property to be new node
            this.first = newNode;
            //set next property on first to be previously created variable
            this.first.next = temp;
        }
        //increment the size of the stack by 1
        return this.size++;
    }
    pop(){
      // if no nodes in stack return null
        if(!this.first) return null;
        // create temp variable to store first property 
        var temp = this.first;
        // if there is only 1 node, set first and last property to null
        if(this.first === this.last){
            this.last = null;
        }
        // if there is more than one node, set the first property to be the next property on the first 
        this.first = this.first.next;
        //decrement size by 1
        this.size--;
        // return value of removed node
        return temp.value;
    }
}

//Stack Implementation with Array (no classes or codes); appropiate for small data sets

var stack = []
stack.push('google')
stack.push('youtube')
stack.push('instagram')
stack.pop()

//basic pushing and pop is stacking, adding to the middle is not; best choice here because doesnt require reindexing

stack.unshift('create new file')
stack.unshift('resize file')
stack.unshift('clone directory')
stack.shift()

//basic unshift and shift is stacking; runtime is not efficient because will be reindexed
###################################################################################################################

## Queues ######################################################################################################
- [X] Understand when to use a queue
- [X] Be familiar with common methods
- [X] Implement a queue
- [] Find and use a queue library
- [X] Discern performance tradeoffs for different implementations of a queue
================================================
Queue -  first in first out 
      - adding and removing
      Methods:
        Dequeue - remove from beginning ("push")
        Endqueue - add to end ("shift"); takes in value
EX: waiting in line, background tasks on computers, print queue
================================================
BIG O / RUNTIME: 
Priorities:
*removal & insertion - O(1) - not constant time in array implementation O(N)

Non-Priorities
*searching & access - O(N)

================================================
//Implementation with an array: both are not great for any performance based scenario

var q = []

//add to beginning or end
q.push('first')
q.push('second')
q.push('third')
//remove from beginning; this will reindex
q.shift()

//this will reindex
q.unshift('first')
q.unshift('second')
q.unshift('third')
q.pop()

Implementation: 
class Node {
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){
      // create a new node using value passed in
        var newNode = new Node(val);
        // if there are no nodes in the queue set new node to be first and last 
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
          // set next property on current last to be new node
            this.last.next = newNode;
            //set last property of queue to be new node
            this.last = newNode;
        }
        //increment by 1
        return this.size++;
    }

    dequeue(){
      //if there is not first property, return null
        if(!this.first) return null;
      //store the first property in a variable
        var temp = this.first;
        //if first same as last equal null
        if(this.first === this.last) {
            this.last = null;
        }
        // if there is more than one node, set the first property to be the next property on the first 
        this.first = this.first.next;
        //decrement by 1
        this.size--;
        // return value of removed node
        return temp.value;
    }
}
###################################################################################################################

## LINKED LISTS ######################################################################################################
- [X] Implement various types of linked lists.
- [] Understand which portions of linked lists are already implemented in JavaScript.
- [X] Implement their own linked lists under the correct circumstances.


DEFINITION DLL:  
-pointer is pointing to previous node and the next node
-need to account for two pointers, so takes more memory
-more flexibility, easier to navigate and find nodes in half the time compared to SLL

BIG O / RUNTIME: 
*insertion - O(1) - easy, take current head or tail and move head or tail, always same amount of time and effort; quicker than array        
*removal - O(1) - if removing from beginning, very simple matter of taking off the head, making it null and reassigning head to second node; always constant unlike SLL because dont have to traverse entire list
*searching - O(N) - iterate through list to check all nodes, as number in list grows, so does time take 
*accesss - O(N) - iterate through list to check all nodes, as number in list grows, so does time take; array has constant random access making access quicker


IMPLEMENTATION: 

class Node{
    constructor(val){
        this.val = val;
        this.next = null; //in the beginning,  the node has no next node to comes after it
        this.prev = null; //in the beginning,  the node has no prev node to comes before it
    }
}

class DoublyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

/* =============== PUSH ===================
INSERTS a new node onto tail and reassign it as newtail by connecting the new node in reverse to previous node tail
   ======================================= */
  push(val){
    //instantiate new node using the value passed to function
    let newNode = new Node(val);
    //if head prop is null, set the head and tail to be the newly created node
    if (!this.head || this.length === 0){
      this.head = newNode;
      this.tail = this.head;
    } 
    //or set the next prop on tail to be new node and tail to new node
    else {
      this.tail.next = newNode;//forward
      //set the previous property on the new node to be the tail
      newNode.prev = this.tail;//backward
      //set the tail to be the newly created node
      this.tail = newNode; //update the tail
    }
    //imcrement the length
    this.length++;
    //return the list
    return this;
  }
/* ================= POP ==================
REMOVES a node from the end of linked list;identify second to last item, remove the tail, reassign second to last as tail; no values need to be taken in because removing and working with whats already present
 ======================================= */

    pop() {
      //if no head, no tail, or length is 0, return undefined
      if(!this.head || !this.tail || this.length === 0) {return undefined}
      //store current tail into variable
      let oldTail = this.tail;
      //if length is 1, set head and tail to be null
      if (this.length === 1){
        this.head = null;
        this.tail = null;
      } else {
      //update the tail to be the previous node
      this.tail = oldTail.prev; //backward
      //set the new tail next to null and then set .prev to null 
      this.tail.next = null; //forward
      //set previous tail to null
      oldTail.prev = null;
      }
      //decrement the length
      this.length--;
      //return value removed
      return oldTail;
    }
  /* =============== SHIFT ================
REMOVES a node from the beginning of linked list; remove head and reassign head to second node immediately after the head; reassign both previous to null
 ======================================= */
    shift(){
      //if length is 0, return undefined
      if(this.length === 0) {return undefined}
      //store current head into variable
      let oldHead = this.head;
     //if length is 1, set head and tail to be null
      if (this.length === 1){
        this.head = null;
        this.tail = null;
      } else {
      //update the head to be the next of old head
      this.head = oldHead.next;
      //set head previous prop to null
      this.head.prev = null; //backward
      oldHead.next = null; //forward
      }
      //decriment the length
      this.length--
      //return old head
      return oldHead;
    }
  /* =============== UNSHIFT ================
INSERTS a node to the beginning of linked list; point the new value at the head and then reassign new value to head
 ======================================= */
    unshift(val){
        //instantiate new node using the value passed to function
        let newNode = new Node(val);
        //if length is 0, set the head and tail to be the newly created node
        if (!this.head || this.length === 0){
          this.head = newNode;
          this.tail = this.head;
        } else {
          //set previous property on head to be new node
          this.head.prev = newNode; //backward
          //set next property on new node to be the head
          newNode.next = this.head; //forward
          //update the head to be the new node
          this.head = newNode //update
        }
    }

}
================================================
DEFINITION SLL: ordered data structure that contains head, tail and length; 
 COMPARISONS:(linked lists are stairs and arrays are elevators)
 -Singly Lists excell at insertion and deletion compared to arrays; dont care about random access, but rather in order access
Lists: 
- made up of nodes that has a value and next pointer at each that points to another node or null, 
- no index, must start with first and move through each node (no random access allowed); 
Arrays: 
- index are mapped to a number in order 
- insertion and deletion expensive
- quick access by index number 

BIG O / RUNTIME: 
*insertion - O(1) - easy, take current head or tail and move head or tail, always same amount of time and effort; quicker than array        
*removal (depends) - O(1) - if removing from beginning, very simple matter of taking off the head, making it null and reassigning head to second node - O(N) - removing from end is more difficult because need to iterate over all items to reassign tail to second to last item
*searching - O(N) - iterate through list to check all nodes, as number in list grows, so does time take 
*accesss - O(N) - iterate through list to check all nodes, as number in list grows, so does time take; array has constant random access making access quicker
================================================
IMPLEMENTATION: 
// piece of data - val
//reference to next node - next

class Node{
    constructor(val){
        this.val = val;
        this.next = null; //in the beginning,  the node has no next node to comes after it
    }
}

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.length = 0;
    }
    
/* =============== PUSH ===================
INSERTS a new node onto head and / or previous nodes
   ======================================= */
    //not ideal way to write code
    // var first = new Node("Hi")
    // first.next = new Node("there")
    // first.next.next = new Node("how")
    // first.next.next.next = new Node("are")
    // first.next.next.next.next = new Node("you")

    push(val){   
        //instantiate new node using the value passed to function
        let newNode = new Node(val);
        //if there is no head prop, set the head and tail to be the newly created node
        if (!this.head){
          this.head = newNode;
          this.tail = this.head;
        } 
        //or set the next prop on tail to be new node and tail to new node
        else {
          this.tail.next = newNode;
          this.tail = newNode;
        }
        //increment length by 1
        this.length++;
        // return list
        return this;
    }

/* ================= POP ==================
REMOVES a node from the end of linked list;identify second to last item, remove the tail, reassign second to last as tail; no values need to be taken in because removing and working with whats already present
 ======================================= */

    pop() {
      //if there arent any nodes in the list, return undefined
      if(!this.head) {return undefined}
      //identify a variable to track node - 1 location
      let current = this.head;
      let newTail = current;
      //loop through the list until you reach the tail
      while(current.next){
        newTail = current; 
        current = current.next;
      }
      //set tail to be the second to last node
      this.tail = newTail;
      //set next property of second to last node to be null  
      this.tail.next = null;
      // decrement length of list by 1
      this.length--;
      if (this.length === 0){
        this.head = null
        this.tail = null
      }
      // return the tail node
      return current;
    }

  /* =============== SHIFT ================
REMOVES a node from the beginning of linked list; remove head and reassign head to second node immediately after the head;no values need to be taken in because removing and working with whats already present
 ======================================= */
    shift(){
      //if there arent any nodes in the list, return undefined
      if(!this.head) {return undefined}
      //store current head property in variable
      let currentHead = this.head;
      //update head property to be the current head's next property
      this.head = currentHead.next;
      // decrement the length by 1
      this.length--;
      if(this.length === 0){
          this.tail = null;
        }
      // return value of removed node
      return currentHead;
    }

      /* =============== UNSHIFT ================
INSERTS a node to the beginning of linked list; point the new value at the head and then reassign new value to head
 ======================================= */
    unshift(val){
        //instantiate new node using the value passed to function
        let newNode = new Node(val);
        //if there is no head prop, set the head and tail to be the newly created node
        if (!this.head){
          this.head = newNode;
          this.tail = this.head;
        } 
        //or set new node's next prop to current head prop
        else {
          newNode.next = this.head;
          //set head property on the list to be new node
          this.head = newNode;
        }
        //increment length by 1
        this.length++;
        //return list
        return this;
    }

}

var list = new SinglyLinkedList();
list.push("HELLO");
// list.push("GOODBYE")

#####################################################################################################################

## Trees #####################################################################################################################
- [] identify, implement and differentiate:
- [] trees
- [] binary tree traversal
- [] binary heaps
- [] tries

## Hash Table #####################################################################################################################
- [] Understand basic hashing algorithms
- [] Know the runtime of hash table operations
- [] Be able to identify problems where hash tables could be used
- [] Be able to write code that uses hash tables to solve problems
- [] Understand how hash tables are implemented and how this implementation leads to the runtime properties

## Deque #####################################################################################################################
- [] Understand when to use a deque
- [] Be familiar with common methods
- [] Implement a deque
- [] Find and use a deque library
- [] Discern performance tradeoffs for different implementations of a deque

## Intro to Algorithms #####################################################################################################################
- [] Understand what an algorithm is.
- [] Understanding what a sorting algorithm is.
- [] Understand the mechanics of a few sorting algorithms including Bubble Sort, Merge Sort, and Quick Sort.
- [] Understand the Runtime Complexity of these algorithms.
- [] Understand how linear and binary search work
- [] Understand the runtime of linear and binary search
- [] Know when to use linear and binary search