Outline

Time	Purpose
9:30am - 10:45pm	Go through Slides
10:45am - 11:00am	Break
11:00am - 1:30pm	Build Linked List
1:30pm - 1:45pm	Break
1:45pm - Until	After Lunch review stacks & queues

Two 15 minute break will be given to learners.

Materials

Lecture Slides

Terminal Objective

Today we will learn about Classes and OOP

Note to Instructor:

Use today to keep talking about Classes

Build The Linked List With Your Students here is your cheat sheet (consider breakout rooms as well, perhaps give them a chance to do it for 30 minutes then do it with them)

LINKED LISTS

Don't forget to highlight these 3 points

Explain what a Linked list is
Demonstrate what a link does
Give an example of a link list implementation can do

What is a Linked List?

A simple often used data structure that has 3 necessary properties
A head
A tail
A size or length property

Linked List Architecture

Linked List consist of element known as nodes
Each node points to the next node in the list if there is no next node it point to null
Nodes have one property known as value or data and contain some primitive value or object value

linked-list

Node Class API

Function	Arguments	Returns	Directions	Example
constructor	(Data, Node)	Node	Creates a class instance to represent a node. The node should have two properties, 'data' and 'next'. Accept both of these as arguments to the 'Node' constructor, then assign them to the instance as properties 'data' and 'next'. If 'next' is not provided to the constructor, then default its value to be 'null'.	const n = new Node('Hi'); n.data // 'Hi' n.next // null const n2 = new Node('There', n); n.next // returns n

LinkedList Class API

Function	Arguments	Returns	Directions	Example
constructor	-	(LinkedList)	Create a class to represent a linked list. When created, a linked list should have no head node associated with it. The LinkedList instance will have one property, 'head', which is a reference to the first node of the linked list. By default 'head' should be 'null'.	const list = new LinkedList(); list.head // null
insertFirst	(data)	-	Creates a new Node from argument 'data' and assigns the resulting node to the 'head' property. Make sure to handle the case in which the linked list already has a node assigned to the 'head' property.	const list = new LinkedList(); list.insertFirst('Hi There'); // List has one node
size	-	(integer)	Returns the number of nodes in the linked list.	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.insertFirst('c'); list.size(); // returns 3
getFirst	-	(Node)	Returns the first node of the linked list.	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.getFirst(); // returns Node instance with data 'a'
getLast	-	(Node)	Returns the last node of the linked list	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.getLast(); // returns node with data 'a'
clear	-	-	Empties the linked list of any nodes.	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.clear(); list.size(); // returns 0
removeFirst	-	-	Removes only the first node of the linked list. The list's head should now be the second element.	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.removeFirst(); list.getFirst(); // returns node with data 'a'
removeLast	-	-	Removes the last node of the chain	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.removeLast(); list.size(); // returns 1 list.getLast(); // returns node with data of 'b'
insertLast	(Data)	-	Inserts a new node with provided data at the end of the chain	const list = new LinkedList(); list.insertFirst('a'); list.insertFirst('b'); list.insertLast('c'); list.getLast(); // returns node with data 'C'
getAt	(integer)	(Node)	Returns the node at the provided index	const list = new List(); list.insertFirst('a'); list.insertFirst('b'); list.insertFirst('c'); list.getAt(1); // returns node with data 'b'
removeAt	(integer)	-	Removes node at the provided index	const list = new List(); list.insertFirst('a'); list.insertFirst('b'); list.insertFirst('c'); list.removeAt(1); list.getAt(1); // returns node with data 'a'
insertAt	(Data, integer)	-	Create an insert a new node at provided index. If index is out of bounds, add the node to the end of the list.	const list = new List(); list.insertFirst('a'); list.insertFirst('b'); list.insertFirst('c'); list.insertAt('Hi', 1) list.getAt(1); // returns node with data 'Hi'

// Linked list

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

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertFirst(data) {
    this.head = new Node(data, this.head);
  }

  size() {
    let counter = 0;
    let node = this.head;

    while (node) {
      counter++;
      node = node.next;
    }

    return counter;
  }

  getFirst() {
    return this.head;
  }

  getLast() {
    if (!this.head) {
      return null;
    }

    let node = this.head;
    while (node) {
      if (!node.next) {
        return node;
      }
      node = node.next;
    }
  }

  clear() {
    this.head = null;
  }

  removeFirst() {
    if (!this.head) {
      return;
    }

    this.head = this.head.next;
  }

  removeLast() {
    if (!this.head) {
      return;
    }

    if (!this.head.next) {
      this.head = null;
      return;
    }

    let previous = this.head;
    let node = this.head.next;
    while (node.next) {
      previous = node;
      node = node.next;
    }
    previous.next = null;
  }

  insertLast(data) {
    const last = this.getLast();

    if (last) {
      // There are some existing nodes in our chain
      last.next = new Node(data);
    } else {
      // The chain is empty!
      this.head = new Node(data);
    }
  }

  getAt(index) {
    let counter = 0;
    let node = this.head;
    while (node) {
      if (counter === index) {
        return node;
      }

      counter++;
      node = node.next;
    }
    return null;
  }

  removeAt(index) {
    if (!this.head) {
      return;
    }

    if (index === 0) {
      this.head = this.head.next;
      return;
    }

    const previous = this.getAt(index - 1);
    if (!previous || !previous.next) {
      return;
    }
    previous.next = previous.next.next;
  }

  insertAt(data, index) {
    if (!this.head) {
      this.head = new Node(data);
      return;
    }

    if (index === 0) {
      this.head = new Node(data, this.head);
      return;
    }

    const previous = this.getAt(index - 1) || this.getLast();
    const node = new Node(data, previous.next);
    previous.next = node;
  }
 // If your hungry for more
  forEach(fn) {
    let node = this.head;
    let counter = 0;
    while (node) {
      fn(node, counter);
      node = node.next;
      counter++;
    }
  }
// If your absolutely starving
  *[Symbol.iterator]() {
    let node = this.head;
    while (node) {
      yield node;
      node = node.next;
    }
  }
}

stack

// --- Directions
// Create a stack data structure.  The stack
// should be a class with methods 'push', 'pop', and
// 'peek'.  Adding an element to the stack should
// store it until it is removed.
// --- Examples
//   const s = new Stack();
//   s.push(1);
//   s.push(2);
//   s.pop(); // returns 2
//   s.pop(); // returns 1

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
    this.data.push(record);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

module.exports = Stack;

Queue

// --- Description
// Create a queue data structure.  The queue
// should be a class with methods 'add' and 'remove'.
// Adding to the queue should store an element until
// it is removed
// --- Examples
//     const q = new Queue();
//     q.add(1);
//     q.remove(); // returns 1;

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop();
  }
}

module.exports = Queue;