[웹개발] JavaScript로 Data structure 구현 (linkedList, hashTable)

Linked List

class Node { //node라는 객체 생성, node는 해당 node가 가지고 있는 value와 그 다음 노드를 가르키는 next로 나뉜다.
  constructor(value) { //let node = new Node(value)를 작성하면 node의 value에 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); //추가할 노드 객체 생성

    if(!this.head) { //head가 비어있다면 비어있는 곳에 노드를 추가하고 사이즈 업
      this.head = node;
      this._size++;
    } 
    else if(!this.tail) { //head는 비어있지 않은데 tail이 비어있다면
      this.head.next = node; //기존 head 노드의 next(기존 null이 할당되어있었음)에 추가하고자 하는 node 할당 : 주소지 할당
      this.tail = node; //비어있던 tail에 추가하고자 하는 node 할당 : 실제 할당
      this._size++; // 사이즈 업
    }
    else { //head, tail 모두 차있는 경우
      this.tail.next = node; // 기존 tail에 있던 노드의 next(기존 null이 할당되어있었음)에 새로 추가할 node 할당 : 주소지 할당
      this.tail = node; //기존 tail에 주소가 추가 됐으니 새로 추가할 node로 바꿔줌. : 실제 할당
      this._size++; // 사이즈 업
    }
  }
  //주어진 값을 찾아서 연결을 해제(삭제)합니다
  remove(value) {
    let currentNode = this.head; //현재 노드 할당
    let prevNode = null; //이전 노드 할당
    
    if(value === this.head.value) { //제거하려는 값이 head에 있을때
      this.head = this.head.next;
      this._size--;
    } else { //제거하려는 값이 head 뒤에 있을 때
      while(currentNode) { //현재 노드가 존재할 때까지 반복 
        if(value === currentNode.value) { //현재 노드의 값과 제거할 값이 같을 때
          prevNode.next = currentNode.next; //이전 노드의 next 에 현재 노드의 next를 할당
          this._size--;
          if (currentNode.value === this.tail.value) { //제거하려는 값이 tail에 있을 때
            this.tail = prevNode; //이미 지정되어 있던 tail의 값을 이전 노드로 변경해줌
          }
          break; //값을 찾았기 때문에 반복문 나옴
        } else { //현재 노드와 제거할 값이 같지 않을 때
          prevNode = currentNode; //이전 노드를 현재 노드로 할당
          currentNode = currentNode.next; // 현재 노드를 다음 노드로 할당 후에 다시 반복문
        }
      }
    }
  }
  //주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 
  //해당 인덱스에 노드가 없다면 undefined를 반환합니다.
  getNodeAt(index) {
    let currentNode = this. head;
    let count = 0; //index와 비교할 값 설정 
    
    while(currentNode) {
      if(index === count) {
        return currentNode;
      }
      currentNode = currentNode.next;
      count++;
    }
  }
  //연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.
  contains(value) {
    let currentNode = this.head;
    
    while(currentNode) {
      if(value === currentNode.value) {
        return true;
      }
      currentNode = currentNode.next;
    }
    return false;
  }
  //주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.
  indexOf(value) {
    let currentNode = this.head;
    let index = 0;

    while(currentNode) {
      if(value === currentNode.value) {
        return index;
      }
      currentNode = currentNode.next;
      index ++;
    }
    return -1;
  }
  //리스트의 노드 개수를 반환합니다.
  size() {
    return this._size;
  }
}

Hashtable

//아래 코드에서 사용된 해시함수
const hashFunction = function(str, max) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash &= hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};

//아래 코드에서 사용된 배열
const LimitedArray = function(limit) {
  const storage = [];

  const limitedArray = {};
  limitedArray.get = function(index) {
    checkLimit(index);
    return storage[index];
  };
  limitedArray.set = function(index, value) {
    checkLimit(index);
    storage[index] = value;
  };
  limitedArray.each = function(callback) {
    for (let i = 0; i < storage.length; i++) {
      callback(storage[i], i, storage);
    }
  };

  var checkLimit = function(index) {
    if (typeof index !== 'number') {
      throw new Error('setter requires a numeric index for its first argument');
    }
    if (limit <= index) {
      throw new Error('Error trying to access an over-the-limit index');
    }
  };

  return limitedArray;
};

// 본 코드 시작
class HashTable {
  constructor() {
    this._size = 0;
    this._limit = 8;
    this._storage = LimitedArray(this._limit);
  }
  //주어진 키와 값을 저장합니다. 이미 해당 키가 저장되어 있다면 값을 덮어씌웁니다.
  insert(key, value) {

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

    const index = hashFunction(key, this._limit); //여기까지 디폴트 값
    let bucket = this._storage.get(index); //인덱스에 저장된 값을 bucket이라는 변수에 할당

    if(bucket) { // 만약 버킷에 값이 있다면
      bucket[key] = value; //버킷(객체)에 키와 밸류 새롭게 추가
      this._storage.set(index, bucket); //내용이 추가된 버킷을 다시 스토리지에 set
    } 
    else { // 버킷에 값이 없다면 
      let newBucket = {}; //새로운 버킷을 만들고
      newBucket[key] = value //키와 밸류 추가
      this._storage.set(index, newBucket); //스토리지에 newBucket 추가. 여기서 바로 객체 모습({key:value} 이런 형태)으로 넣으려고 했으나 실패
    }

  }
  //주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
  retrieve(key) {
    const index = hashFunction(key, this._limit); //여기까지 디폴트 값
    let bucket = this._storage.get(index); //매개변수 key에 해당하는 버킷 가져옴
    let result ; // 결과값 변수 선언

    for(let tuple in bucket) { //버킷에 저장된 key를 기준으로 도는 반복문
      if(key === tuple) { //매개변수 key와 버킷에 저장된 key=tuple이 같으면
        result = bucket[tuple]; //결과값에 key에 해당하는 value 할당
        break; //반복문 종료
      } 
    }

   return result; //결과값 리턴
  }
  // 참고 코드
  // retrieve(key) {
  //   //주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
  //   const index = hashFunction(key, this._limit);
  //   return this._storage.get(index)[key];
  // }


  //주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
  remove(key) {

    if(this._size <= this._limit * 0.25) {
      this._resize(parseInt(this._limit * 0.5));
    } 

    const index = hashFunction(key, this._limit); // 여기까지 디폴트 

    let bucket = this._storage.get(index); //매개변수 key에 해당하는 버킷 가져옴
    let deletion; //지울 값 변수 선언

    for(let tuple in bucket) { //버킷에 저장된 key를 기준으로 도는 반복문
      if(key === tuple) { //매개변수 key와 버킷에 저장된 key=tuple이 같으면
        deletion = bucket[tuple]; //지울 값에 해당 value 할당 후에
        delete bucket[tuple]; //해당 키값쌍 삭제
        break; //반복문 종료
      } 
    }
 
    this._size--;
    return deletion; //할당해놨던 지울 값 리턴
  }
  //참고 코드
  // remove(key) {
  //   //주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
  //   if(this._size / this._limit <= 0.25) {
  //     this._resize(parseInt(this._limit/2));
  //   }
  //   const index = hashFunction(key, this._limit);
  //   let el = this._storage.get(index);
  //   let retrieve = el[key];
  //   delete el[key];
  //   this._size--;
  //   return retrieve;
  // }

  //해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수입니다. 
  //리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 
  //구현 후 HashTable 내부에서 사용하시면 됩니다.
  _resize(newLimit) {
    let oldStorage = this._storage; //기존 스토리지를 다른 변수에 저장

    this._size = 0; //사이즈 초기화
    this._limit = newLimit; //리밋을 새로 들어오는 변수값으로 저장
    this._storage = LimitedArray(this._limit); //스토리지를 주어진 리밋으로 다시 설정
  
    oldStorage.each((bucket) => { 
      for(let tuple in bucket) { 
        this.insert(tuple, bucket[tuple]); //여기서 this를 사용하려면 두줄 위의 화살표 함수로 작성해야만 함.
      }
    });
  }
}

출처 : [codestates] software engineer immersive course sprint