TIL 09. Data Structure02. Linked List, Hash Table

five1star·2020년 9월 5일
0

TIL

목록 보기
9/25
post-thumbnail

Codestates Immersive 두번째 스프린트 Data Structure의 두번째날. 오늘은 LinkedList, Hash Table을 구현한다.

1.Linked List

연결 리스트는 크기가 동적인 자료구조로, N개의 Node와 Node의 연결로 이루어졌다. 연결리스트는 형태가 배열과 매우 유사하지만, 인덱덱스를 갖지 않는다는 특징이 있다.

1) 배열과 연결리스트의 차이점

결론: 삽입과 제거가 빈번히 일어난다면 연결리스트가, 만들어진 구조에서 접근이 중요한
데이터라면 배열을 사용하는것이 좋다.

2) 연결리스트의 종류 * 이중연결리스트에대해 공부 필요

단일연결리스트 : 노드가 한방향으로 연결됨

이중연결리스트 : 이전 노드와 다음 노드가 상호 연결됨

3) 단일연결리스트의 구현(의사코드)

class Node {
  constructor(value) {
    this.value = value; //한 노드의 벨류
    this.next = null; //한 노드가 가르치는 다음 노드
  }
}

class LinkedList {
  constructor() {
    this.head = null; //빈 리스트가 아니라면 head는 항상 값을 가진다.
    this.tail = null; //마지막 노드의 tail은 항상 null
    this._size = 0; //노드가 추가되면 사이즈가 ++, 노드가 삭제되면 사이즈가 --
  }

  addToTail(value) {
    새로운 노드를 생성한다.
    if(만약 사이즈가 0이라면(리스트에 노드가 하나도 없으면)){
      방금 생성한 노드는 head가 된다
      } else {
       만약 기존에 노드가 있었다면
       마지막 테일이 가르치던 next가 null에서 새로운 노드로 향한다
      }
    테일 = 새로만든 노드가 된다.
    사이즈를 ++한다.
  }

  remove(value) {
    if(헤드의 벨류 === 벨류){
      헤드를 temp변수에 담아 임시 저장한다
      헤드는 헤드의 넥스트가 된다.
      사이즈를 줄인다
      삭제할 노드를 출력한다.
      (이전 head 노드는 아무도 지정하지 않기 때문에 둥둥 떠다님)
    } 벨류가 어딘가에 있다면?
     헤드를 temp 변수에 잡아준다
    while(만약 헤드 다음 벨류 !== 벨류){
      temp는 temp.next로 할당한다
    }
    사이즈를 줄인다.

    if(만약, value를 가진 노드가 tail이라면?) {
      마지막 노드를 result로 잡고
      tail을 마지막 노드가 아니라 그 전 노드로 바꿔준다.
      테일의 next를 null로 바꿔 연결을 끊는다.
      삭제된 resultfmf 출력한다.
    }

    (while문 다음에, 첫 이프문의 연속)
    해당 노드를 변수로 잡아준다.
    해당 노드 전의 노드의 next를 해당 노드의 다음 노드에 연결한다.
    value를 가진 해당노드(삭제할노드)를 출력한다.
  }

  getNodeAt(index) {
    if(만약 인덱스 넘버가 사이즈보다 크면){
      undefined를 리턴한다
    }
    
    if(만약 index===0)이면{
      head 노드를 출력한다.
    }
    
    헤드를 result에 담아준다.
    for (for문으로 인덱스 넘버가 될때까지 돌린다){
      그만큼 head를 head.next로 옮긴다.
    }
    해당 노드를 출력한다.
  }

  indexOf(value) {
    head를 변수에 담아준다.
    for (사이즈의 숫자만큼 끝까지 for문을 돌린다.) { 
      if (만약, head의 value가, 찾는 value라면) {
        i를 출력한다
      } 아니라면
      head를 하나 next로 옮긴다
    }
    아무것도 없다면 -1를 출력한다.
  }

  contains(value) {
    false값을 가진 변수를 설정한다.

    for (처음부터 size 끝까지 검색한다.) { 
   모든 노드를 살펴보며, value값과 동일한 노드가 있으면 result를 true로 바꾼다
    }
    boolean값을 출력
  }

  size() {
   사이즈를 출력하다.
  }
}

주의할점

2.Hash Table

해시 테이블은 키, 값 쌍을 저장하고 있는 자료 구조다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환해 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

설명을 보면 어렵지만 이런느낌

한정된 메모리공간에 데이터를 저장할때 중간값이 비어있다면 이런 문제가 생긴다.

let arr = [];
undefined
arr[5] = 1
1
arr
(6) [empty × 5, 1] 

지금은 empty가 5공간을 차지하지만, 만약 arr[10000]=1 과 같은 값을 넣는다면?

arr[100000000]=1
1
arr
(100000001) [empty × 5, 1, empty × 99999994, 1]

어마어마한 공간낭비가 생긴다.

해시테이블은 데이터 낭비를 해결하는데 최적화된 데이터 저장 구조다.
해시 테이블 안에서 핵심은 해시 함수인데, 특정 키값과 벨류를 넣으면, 해시 함수를 통해 한정된 array의 몇번 인덱스에 내용을 배정할지 결과값을 리턴한다. 해당 값은 해시함수로 나온 인덱스에 저장된다. 따라 해시테이블의 가장 중요한 요소는 어떤 키와 벨류를 넣었을때, 항상 동일한 값이 나오고, 한정된 어레이공간에 적절히 배정해줄수있는 해시함수가 얼마나 잘 짜여져있는지에 달렸다.

해시테이블은 마치 기숙사 방배정과 같은 느낌...

해시 테이블에 있어 중요한 다른 하나는 공간을 적절히 유지해주어야한다는것이다. 한정된 공간을 적절히 사용하기 위한 목적으로 만들어진것이기때문에, 전체 어레이의 공간이 항상 쾌적한 상태로 유지되어야한다.

해시테이블의 한정된 공간은 25~75% 가용률이 유지되는것이 적합하기때문에, 75%이상 배정되었다면 리사이즈를 통해 사이즈를 늘려주고, 25%미만이라면 사이즈를 줄여주는 작업을 상황에 따라 반복해야한다.

해시테이블의 구현(의사코드)

해시테이블은 아직 구현이 끝나지 않아 마치면..
profile
자라나라 코드코드

0개의 댓글