WHATIS. DATASTRUCTURE


1. Stack



要素を追加すると、スタックが上部から追加されます.
要素を取り除く(取り出す)ときに、上から取り除く資料構造.(LIOF)
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.

1-1. インプリメンテーション

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

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

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

  pop() {
    const last = this.storage[this.top]
    delete this.storage[this.top]
    this.top--
    return last
  }
}

2. Queue



要素を追加すると、キューが後に追加されます.
要素を除去(取り出し)すると、前から除去されます.(FIFO)
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.

2-1. インプリメンテーション

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

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

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

  dequeue() {
    let result = this.storage[this.front];
    delete this.storage[this.front]; 
    if (this.front < this.rear) {
      this.front++;
    }
    return result;
  }
}

3. Linked List



リンクリストは複数のノードで構成されています.
ノードはKey(value)とNext(Pointer)からなり、次のノードを指す.
このとき、Nextは前のノードと後のノードを指すことができる.
これをDouble-Linkリストといいます.
筆者は簡単なリンクリストの基準で説明する
リンクリストの最初のものをheadと呼び、headは最初のノードを表します.
(もちろん、最初のノード自体はHeadであってもよい.)
ノードのNextがNullである場合、このノードはTailと呼ばれる.
この構造をLinked-Listと呼ぶ.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得するとO(n)の時間的複雑さがある.

3-1. インプリメンテーション

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

  addToTail(value) {
    let node = new Node(value)
    this._size ++;
    // 1. 처음으로 추가할 때, head에 node 할당
    if (this.head === null) {
      this.head = node;
    }
    // 3. 앞에 node가 이미 있는 경우. 
    if (this.tail !== null) {
      this.tail.next = node;
      this.tail = node;
    } 
    // 2. 새로운 노드가 추가될 때마다 tail에 node 할당
    else {
      this.tail = node;
    }
  }

  remove(value) {
    if (this._size > 0) {
      if (this.head.value === value) { // 헤드의 벨류가 같을 때
        this.head = this.head.next; // 헤드를 다음 노드로 변경하기
        this._size--;
      }
      else {
        let prevHead = this.head;
        let newHead = this.head.next;
        let size = this._size;
        while (size) {
          if (newHead.value === value) { // value 일 경우
            if (newHead.next === null) {
              prevHead.next = null;
              prevHead = false;
              this.tail = prevHead;
              this._size--;
              }
            else {
              prevHead.next = newHead.next;
              newHead.next = null;
              //newHead = false;
              this._size--;
            }
            break;
          }
          else if (newHead.value !== value) { // value 아닐 경우
            prevHead = this.head.next.next;
            size--;
          }
        }
      }
    }
  }

  getNodeAt(index) {
    let checkHead = this.head
    while(index > -1) {
      if (index === 0 && this.head !== null) {
        return checkHead;
      }
      if (index > 0) {
        index--
        if (checkHead.next === null) {
          return undefined;
        }
        checkHead = checkHead.next;
      }
    }
    return undefined;
  }

  contains(value) {
    let size = this._size
    let checkHead = this.head
    while (size) {
      if (checkHead.value === value) {
        return true;
      }
      else {
        checkHead = checkHead.next;
      }
      size--
    }
    return false;
  }

  indexOf(value) {
    let size = this._size
    let result = 0
    let checkHead = this.head
    while (size) {
      if (checkHead.value === value) {
        return result;
      }
      else {
        checkHead = checkHead.next;
        result++
      }
      size--
    }
    return -1;
  }

  size() {
    return this._size;
  }
}

4. Hash Table



ハッシュテーブルは、データを格納する際にハッシュ機能、格納を使用します.
Hash Functionは入力したデータをHash値に置き換えます.
Hash値をStorageのIndex値にマッピングします.
次に、対応するインデックスにデータを入れます.
このとき、入力したデータをHash値に変換し、複数のindex値にマッピングします.
2つ以上の値が1つのインデックスに入る競合が発生しました.
(もちろん、目的によってカバーすることもあります.)
この問題を解決する方法は二つに分かれている.
1. Open Addressing
:2つの競合値のうちの1つを別の空のインデックスに挿入する方法.
2. Separate Chaining
:2つの値を1つのインデックスにリンクする方法.
値を追加すると、O(1)の時間的複雑さがあります.
値を除去するとO(1)の時間的複雑さがある.
特定の値を取得する場合,O(1)の時間的複雑さを持つ.

4-1. インプリメンテーション

const LimitedArray = require('./helpers/limitedArray');
const hashFunction = require('./helpers/hashFunction');
// 위 문법은 helpers 폴더에 있는 limitedArray와 hashFunction을 불러오는 문법입니다.
// 위와 같이 require를 사용해서 다른 파일로부터 함수 등을 불러오는 작업은 이후에 따로 설명합니다.
class HashTable {
  constructor() {
    this._size = 0;
    this._bucketNum = 8;
    this._storage = LimitedArray(this._bucketNum);
  }
  insert(key, value) {
    const index = hashFunction(key, this._bucketNum); // 0, 1, 2, 3, ...
    let obj = {}
    if (this._storage.get(index) === undefined) {
      obj[key] = value;
      this._storage.set(index, obj)
    } else {
      obj = this._storage.get(index)
      obj[key] = value;
      this._storage.set(index, obj)
    }
    this._size++;
    //this._resize(this._bucketNum);
    // 추가
    if (this._bucketNum * 0.75 <= this._size) {
      this._resize(this._bucketNum * 2)
    } 
  }
  retrieve(key) {
    const index = hashFunction(key, this._bucketNum);
    if (this._storage.get(index) === undefined) {
      return undefined;
    }
    return this._storage.get(index)[key];
  }
  remove(key) {
    const index = hashFunction(key, this._bucketNum);
    delete this._storage.get(index)[key];
    this._size--;
    // 추가
    if (this._bucketNum * 0.25 > this._size) {
      this._resize(this._bucketNum * 0.5);
    }
  }
  _resize(newBucketNum) {
    let past = this._storage;
    this._size = 0;
    this._bucketNum = newBucketNum;
    this._storage = LimitedArray(this._bucketNum); // new storage
    // 해싱
    past.each(function(past){
      for (let i in past) {
        this.insert(i, past[i])
      }
    }.bind(this))
  }
}

5. Graph



グラフは複数のノードで構成されています.
また,これらのノード間の関係にはedge(幹線)がある.
edgeは一方向でも双方向でもよい.
(幹線に方向がある場合は、直接図形またはUndirect図形)
グラフの代表的な実装方法は2つに分けられます.
1.隣接行列
:2 D配列で表現する方法.(無幹線は0、有幹線は1)
O(1)だけで2つの頂点の間に幹線が存在するかどうかを知ることができるという利点がある.
定点の差はO(n)で、すべての幹線の数はO(n^2)が必要です.
2.隣接表
:各頂点に隣接する頂点をリスト化する方法.(作成者が使用)
2つの頂点を結ぶ幹線の有無や回数を知るためにはO(n)が必要である.
すべての幹線の数にはO(n+e)が必要です.(e=幹線数)
実施方法は、通常、目的に応じて選択される.

5-1. インプリメンテーション

class Graph {
  constructor() {
    /*
     *  ex)
     *    nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     */
    this.nodes = {};
  }

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

  contains(node) { // 해당노드가 들어있는지 유무 리턴
    return node in this.nodes;
  }

  removeNode(node) {
    delete this.nodes[node];
    for (let key in this.nodes) {
      if (this.nodes[key].includes(node)) {
        this.nodes[key].splice(this.nodes[key].indexOf(node), 1);
      }
    }
  }

  hasEdge(fromNode, toNode) {
    if (this.nodes[fromNode] !== undefined && this.nodes[toNode] !== undefined) {
      return this.nodes[fromNode].includes(toNode) && this.nodes[toNode].includes(fromNode);
    }
    return false;
  }

  addEdge(fromNode, toNode) {
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

  removeEdge(fromNode, toNode) {
    this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1)
    this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1)
  }
}

5. Tree



ツリーはグラフの一部であり、階層化された資料構造です.
同様に、複数のノードで構成され、上部にルートノードが作成されます.
childをルートに接続して実装します.
Leafと呼ばれるサブノードはありません.
最下部にサブノードがないノードをSibligsと呼ぶ.
ツリーのタイプ
1. Binary tree
2. Binary Search Tree
3. Balance
4. Complete binary tree
5. Full binary tree
6. Perfect binary tree
7. Binary tree traversal
木の遍歴方法
1.Inorder(中位数):Left、Root、Right(LRootr)
2.Preorder(前輪):Root、Left、Right(RootLR)
3.Postorder(後列):Left、Right、Root(LR Root)
ツリーの種類と巡回方法の詳細については、ここです。を参照してください.

5-1. インプリメンテーション

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

  insertNode(value) {
    let node = new TreeNode(value);
    this.children.push(node);
  }

  contains(value) {
    let result = false;
    if (this.value === value) {
      return true;
    }
    for (let i = 0; i < this.children.length; i++){
      result = this.children[i].contains(value)
      if (result !== false) {
        return result;
      }
    }
    return false;
  }
}