IM - data-structure

• Queue
• stack
• hashTable
• linkedList
• BST
• graph
• tree

---

Queue

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length;
    //reference:  return this.rear - this.front;
  }

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
  }

  dequeue() {
    if(this.size() === 0){
      this.front = this.rear;
      return undefined;
    }
    //reference:
    // if (this.size() === 0) {
    //   return;
    // }
    const deletedVal = this.storage[this.front];
    delete this.storage[this.front];
    this.front++;
    return deletedVal;
  }
}

 

---

stack

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }

  size() {
    return Object.keys(this.storage).length;
  }

  push(element) {
    this.top++;
    this.storage[this.top] = element;
  }

  pop() {
    if(this.size() === 0){
      this.top = -1;
      return undefined;
    }
    //reference:
    // if (this.size() <= 0) {
    //   return;
    // }
    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top--;

    return result;
  }
}

hashTable

본인이 작성한 코드와 레퍼런스 코드의 비교

가장 큰 차이점은 버킷을 객체로 쓰느냐 배열로 쓰느냐 의 차이.

---

linkedList

레퍼런스코드

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

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

  addToTail(value) {
    const newNode = new Node(value);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this._size += 1;
  }

  remove(value) {
    const index = this.indexOf(value);
    if (index === -1) {
      return;
    }

    if (index === 0) {
      if (this.head === this.tail) {
        this.head = null;
        this.tail = null;
        this._size = 0;
      } else {
        this.head = this.head.next;
        this._size -= 1;
      }

      return;
    }

    const prevNode = this.getNodeAt(index - 1);
    const removedNode = prevNode.next;

    if (removedNode === this.tail) {
      prevNode.next = null;
      this.tail = prevNode;
      this._size -= 1;
      return;
    }

    prevNode.next = removedNode.next;
    this._size -= 1;
  }

  getNodeAt(index) {
    let counter = -1;

    let currentNode = this.head;
    while (currentNode) {
      counter += 1;
      if (index === counter) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    return undefined;
  }

  contains(value) {
    return this.indexOf(value) !== -1;
  }

  indexOf(value) {
    let index = 0;

    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.value === value) {
        return index;
      }
      index += 1;
      currentNode = currentNode.next;
    }

    return -1;
  }

  size() {
    return this._size;
  }
}

 

---

Binary Search Tree

레퍼런스코드

class BinarySearchTreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insert(value) {
    if (value < this.value) {
      if (this.left === null) {
        this.left = new BinarySearchTreeNode(value);
      } else {
        this.left.insert(value);
      }
    } else if (value > this.value) {
      if (this.right === null) {
        this.right = new BinarySearchTreeNode(value);
      } else {
        this.right.insert(value);
      }
    } else {
      // do nothing: The tree already contains this value
    }
  }
  //root => left => right 순으로 value 여부를 확인하는데(전위순회), 
  //recursion 을 사용하여 깊이 탐색한다. 시간복잡도는 O(logn) 을 갖는다. 
  contains(value) {
    if (value === this.value) {
      return true;
    }
    if (value < this.value) {
      return !!(this.left && this.left.contains(value));
    }
    //자바스크립트에서 느낌표두개(!!)는 다른 타입의 데이터를 Boolean 타입으로 
    //명시적으로 형 변환(Type Conversion)하기 위해 사용합니다. 
    if (value > this.value) {
      return !!(this.right && this.right.contains(value));
    }
  }

  inorder(callback) {
    if (this.left) {
      this.left.inorder(callback);
    }
    callback(this.value);
    if (this.right) {
      this.right.inorder(callback);
    }
  }
}
/* callback 
    let arr = [];
    let cb = function (value) {
      arr.push(value);
    };
    
    arr = [3, 5, 7, 8, 10, 11, 14, 15, 16];
*/

 

---

Graph

레퍼런스 코드

/* Undirected Graph */
class Graph {
  constructor() {
    this.nodes = {};
  }

  addNode(node) {
    this.nodes[node] = this.nodes[node] || [];
  }

  contains(node) {
    return !!this.nodes[node];
  }

  removeNode(node) {
    if (this.contains(node)) {
      for (let i = 0; i < this.nodes[node].length; i += 1) {
        this.removeEdge(this.nodes[node][i], node);
      }
      delete this.nodes[node];
    }
  }
  //fromNode가 toNode Edge를 가지고 있는지 여부 확인 
  hasEdge(fromNode, toNode) {
    if (!this.contains(fromNode)) {
      return false;
    }
    return !!this.nodes[fromNode].includes(toNode);
  }

  addEdge(fromNode, toNode) {
    //this가 fromNode 와 toNode를 포함하고 있다면, 아래 if구문을 통과한다. 
    if (!this.contains(fromNode) || !this.contains(toNode)) {
      return;
    }

    // Add an edge to each node pointing to the other
    if (!this.hasEdge(fromNode, toNode)) {
      this.nodes[fromNode].push(toNode);
    }

    if (!this.hasEdge(toNode, fromNode)) {
      this.nodes[toNode].push(fromNode);
    }
  }

  removeEdge(fromNode, toNode) {
    //this가 fromNode 와 toNode를 포함하고 있다면, 아래 if구문을 통과한다. 
    if (!this.contains(fromNode) || !this.contains(toNode)) {
      return;
    }

    // Remove edges from each node's edge list
    if (this.hasEdge(fromNode, toNode)) {
      const index1 = this.nodes[fromNode].indexOf(toNode);
      this.nodes[fromNode].splice(index1, 1);
    }

    if (this.hasEdge(toNode, fromNode)) {
      const index2 = this.nodes[toNode].indexOf(fromNode);
      this.nodes[toNode].splice(index2, 1);
    }
  }
}

 

---

Tree

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  insertNode(value) {

    const curNode = new TreeNode;
    curNode.value = value;
    this.children.push(curNode);

  }
  //방법1 
  contains(value) {

    let result = false;

    function recursion(element) {

      if(element.value === value){
        result = true;
        return;
      }
      if(element.children.length > 0){
        for(let i = 0; i < element.children.length; i++){
          recursion(element.children[i]);
        }
      }
    }
    recursion(this);
    return result;
  }
  /*방법2 (레퍼런스 코드)
    contains(value) {
    if (this.value === value) {
      return true;
    }

    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
    return false;
  }*/
}