TIL_200504(월) - LinkedList, HashTable 공부 및 구현

LinkedList

크기가 동적인 자료구조이며 노드는 값과 포인터(참조)를 가진다... 소크리에티브 문제를 생각보다 많이 틀렸다. 내일 다시 공부해 보는 시간을 가질 생각이다...

구현 정말... 어려웠다. 이 문제는 앞의 queue와 stack과 함께 블로깅을 할 생각이다.

우선 LinkedList는

1. 노드를 만든다 노드는 값을 나타내는 value와 다음 값 참조를 나타내는 next로 이루어진다.
2. 리스트는 head와 tail로 구성되어 있는데, 노드의 추가는 우선 tail 쪽으로 하면 노드를 추가시키고 tail을 새로 추가된 노드로 한다.

Hashmap

해시함수의 충돌을 구현하는 과정을 진행 중이다.
각 tuple에 들어가는 값을 객체로 지정했더니 resize하는 함수가 진행이 안되서 다시array로 바꾸는 작업을 하고 있다.

HashTable은
1. 해시 함수는 구현되어 있다.(해시 테이블로 인해 인덱스를 얻게 된다.)
2. key와 value를 한 쌍으로 object에 집어넣고 해시함수로 얻은 인덱스에 삽입한다.
3. remove와 retrieve 모두 구현했는데, resize를 못해서 다시 구현하는 것을 공부중이다...

진행한 부분

insert(key, value) {
    const index = hashFunction(key, this._limit); // 인덱스 만들기
    let existValue = this._storage.get(index);
    let object = {};
   
    if (!existValue) { 
      object[key] = value; 
      this._storage.set(index, object); 
      this._size++;
    } else { 
      object = existValue;
      object[key] = value; 
      this._storage.set(index, object); 
      this._size++;
    }

    if(this._size > this._limit * 0.75){
      this._resize(this._limit * 2)
    }
  }

  retrieve(key) {
    const index = hashFunction(key, this._limit);
    return this._storage.get(index)[key];
    
    
  }

  remove(key) {
    const index = hashFunction(key, this._limit);
    delete this._storage.get(index)[key];
    this._size--;

    }
  }