Data Structure를 정리해보자. // Part2

Data Structure,

여러 데이터들의 묶음을 어떻게 사용하고 저장할지 정의한 것.

3. Linked List

각각의 Node들이 하나의 고리로 연결된 구조.
음악 플레이리스트를 생각하면 된다.
Linked List도 음악 플레이리스트와 마찬가지로 하나의 노드(음악)씩 순환한다.

Node는 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로 받는다.
저장할 위치에 주어진 Key를 Hash Function을 통해 Hash Value를 받아 그 Value를 저장한다.
*객체와 유사하지만 객체와 다른 점은 Hash Function 통해 정형화된 Hash Value를 받는다.
이를 Hashing이라 한다.

*Hahsing은 데이터 관리를 위해서 필요하며,
다양한 길이의 데이터를 고정된 형태의 데이터로 Mapping하는 작업이다.
그리고 이를 구현하는 함수를 Hash Function이라고 한다.

아래 그림을 한 번 보자.

사이즈가 10인 Hash Table이 있다.

'복숭:츄르'라는 key-value pair가
Hash Function을 통해 1이라는 Hash Value를 받았고
Hash Table의 1에 value를 저장한다.

나머지 key-value pair도 마찬가지.

Hash Table의 치명적인 단점은 Hash Collision(충돌)이 발생할 수도 있다는 것이다.
서로 다른 key-value pair가 주어졌다 하더라도 같은 Hash Value가 나올 수 있기 때문에 충돌을 처리할 방법을 꼭 생각해야 한다.

아래는 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]);
        }
      }
    })
  }
}