Data Structureを整理してみましょう.//Part2

Data Structure,

複数のデータセットの使用と格納方法を定義します.

3. Linked List

各ノードはリングの構造に接続されています.
音楽のプレイリストを考えればいいです.
リンクリストも音楽プレイリストと同様に、1つのノード(音楽)をループします.
ノードはdata(値)とnext(次のアドレスを指す)を有する.
*tailの場合はnext値はありません.
以下にLinked Listの基本的な方法を示します.

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

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;   
    this._size = 0;
  }
  
  addToTail(value) {
    //새로운 노드를 만든다.
    let node = new Node(value);
    
    //List가 비어있으면
    //node를 추가하고 그 값을 head로 한다.
    if(this.head === null) {
      this.head = node;
      this.tail = node;
      this._size++;
    } else {
    //List가 비어있지 않다면
    //head의 next값을 node에 추가하고
    //그 값을 tail로 한다.
      this.head.next = node;
      this.tail = node;
      this._size++;
      }
      return node;
 }
 
  remove(value) {
    // linked list에서 주어진 value를 찾아 삭제
    //1. linked list에 Node가 존재하지 않을 경우
    //2. linked list에 Node가 존재 할 경우
    //2-1. head의 value가 전달인자의 value랑 같은 경우
    //2-2. 전달인자의 value값이 head에 없을 경우

    if(this.head === null) {
      return undefined;
    } 
    if(this.head.value === value) {
      this.head = this.head.next;
      this._size--;
    }

    let current = this.head;
    let _next = this.head.next;

    while(_next) {
      //삭제하고자 하는 value값이 head의 다음에 있다면 
      //head의 next를 value값이 있는 node 다음으로 연결
      if(_next.value === value) {
        current.next =_next.next;
        this._size--;
        //조건이 충족되면 break
        break;
      } else {
        //그게 아니라면 한 칸씩 밀어서 다시 while문 작동
        current = _next;
        _next = _next.next;
      }
    }
  }
  
  getNodeAt(index) {
    //주어진 index에 있는 값을 리턴
    if(this._size < index) {
      return undefined;
    }
    let current = this.head;
    for(let i = 0; i < index; i++) {
      current = current.next;
    }
    return current;
  }
  
  contains(value) {
    //주어진 value가 포함되어있는지 확인
    let current = this.head;
    let _next = this.head.next;

    while(_next) {
      if(current.value === value) {
        return true;
        break;
      } else {
        current = _next;
        _next = _next.next;
      }
    }
    return false;
  }
 
  indexOf(value) {
    //주어진 value값이 있는 node의 index 리턴
    for (let i = 0; i < this._size; i++) {
      let getNode = this.getNodeAt(i);
      if (getNode.value === value) {
        return i;
        }
      }
      return -1;
    }

  size() {
    return this._size;
  }
}

4. Hash Table

Hash Tableは、割り当てられた空間にデータを格納する.
これらのデータはKeyとValueで受信されます.
Hash FunctionでHash Valueを受信し、指定した鍵を保存する場所に保存します.
*オブジェクトと似ていますが、オブジェクトとは異なり、構造化されたHash ValueがHash Functionによって得られます.
これはHashingと言います.
*韓興はデータ管理が必要です.
異なる長さのデータを固定形式のデータにマッピングする操作.
それを実現する関数をHash Functionと呼ぶ.
下図を見てください.

10番のHash Tableがございます
「福崇:チャール」という名前のkey-valuepair
Hash Functionで1というHash Valueを獲得しました.
Hash Tableの1にvalueを格納します.
残りのkey-value pairもそうです.
Hash Tableの致命的な欠点は、Hash Collision(衝突)が発生する可能性があることです.
異なるkey-valuepairがあっても、同じハッシュ値が現れる可能性があるので、競合を処理する方法を考えなければなりません.
次はHash Tableの基本的な方法です
LimitedArrayとHashFunctionはさらに説明する必要があるかもしれません.
コードの大まかな流れを理解すればよい.

class HashTable {
  constructor() {
    this._size = 0; 
    this._limit = 8; 
    this._storage = LimitedArray(this._limit); // 객체의 형태
  }

  //삽입: 주어진 key와 value를 해시함수의 결과값 인덱스의 bucket에 저장한다. bucket은 linkedlist, [key, value] 쌍은 Node 형태로 저장 {key: key, value: value, next: ~ }
  insert(key, value) {
    //insert 할 때 resizie
    //size를 limit로 나눈 값이 75%이상이면 limit를 두배로 늘린다.
    if(this._size / this._limit >= 0.75) {
      this._resize(this._limit * 2);
    }
    const index = hashFunction(key, this._limit);
    //index값에 접근할 수 있는 변수 설정
    let bucket = this._storage.get(index);
    let tuple = [key, value];
    //bucket에 데이터가 없을 경우, set 메소드로 추가.
    if(bucket === undefined) {
      this._storage.set(index, [tuple])
    }
    //bucket에 데이터가 있을 경우, 
    //  1. key가 같을 경우, 기존 value값을 덮어쓴다.
    //  2. key가 다를 경우, bucket 안에 linked list에 추가.
    else {
      for(let i = 0; i < bucket.length; i++) {
        if(bucket[i][0] === key) {
          bucket[i][1] = value;
        } else {
          bucket.push(tuple);
        }
      }
    }
    //추가할 때 마다 사이즈 증가.
    this._size++;
  }
  // 탐색: 원하는 key에 해당하는 value를 찾는 연산
  retrieve(key) {
     //주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
    const index = hashFunction(key, this._limit);
    let bucket = this._storage.get(index)
    let result;

    //key가 주어지면 value를 리턴.
    //주어진 key에 value가 없으면 undefined.
    //                  있으면 value 리턴.
    if(bucket === undefined) {
      return undefined;
    } else {
      for(let i = 0; i < bucket.length; i++) {
        if(bucket[i][0] === key) {
          result = bucket[i][1]
        }
      } 
    } 
    return result; 
  }
    
  remove(key) {
    if(this._size / this._limit <= 0.25) {
      this._resize(this._limit / 2);
    }
    const index = hashFunction(key, this._limit);
    let bucket = this._storage.get(index)
    let result = undefined;

    for(let i = 0; i < bucket.length; i++) {
      if(bucket[i][0] === key) {
      result = bucket[i][1];  
      bucket.splice(i, 1);
      this._size--;
      }     
    }
    return result;
  }

  _resize(newLimit) {
    let current_storage = this._storage;
    this._limit = newLimit;
    this._size = 0;
    this._storage = LimitedArray(newLimit);


    current_storage.each(bucket => {
      if(bucket) {
        for(let i = 0; i < bucket.length; i++) {
          this.insert(bucket[i][0], bucket[i][1]);
        }
      }
    })
  }
}