DevLog__[Data Structure: Linked List, Hash Table]

Jaewon Lee·2020년 10월 27일
0

Data Structure

목록 보기
2/3
post-thumbnail

# Intro

오늘도 오지게 달려보자....짧아져 가는 나의 intro..

😩😩😩


1. Linked List


1. 연결리스트(Linked List)란?

  • 연결 리스트는 각 노드가 데이터와 포인터(주소값)를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
  • 위에 그림처럼 생긴 것이 노드(Node), data로 적힌 부분에 원하는 값을 넣고 화살표로 되어 있는 부분은 다음 노드를 가리키는 주소값이 들어있다.
  • 비엔나 소세지 마냥 줄줄이 매달면 이런 모양새가 나옴.

2. 연결리스트 종류

단일연결리스트

  • 단일 연결 리스트는 각 노드에 data 공간과 한 개의 포인터(주소값) 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

이중연결리스트

  • 이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만, 포인터(주소값) 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

원형연결리스트

  • 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

3. 배열 vs 리스트

  • 두 가지 모두 순차적으로 데이터를 저장한다.
  • 둘의 차이는 메모리 사용에 있다. 배열은 메모리에 사용량을 미리 정해주어야 하는 반면에, 리스트는 input에 따라 유동적으로 메모리 사용량을 결정할 수 있다.
  • 이로 인해 생기는 장점과 단점은 위에 표를 통해 정리했다.

4. 연결리스트의 시간 복잡도(Time Complexity)

1) Access : O(n)

  • 리스트는 배열처럼 index가 존재하지 않기 때문에 head부터 접근해야 한다.
  • 10이라는 값을 가진 노드에 접근하기 위해서는 5번을 움직여야 한다.
  • 접근하려는 노드가 n번째에 위치한다면, n번을 움직여야하기 때문에 시간복잡도는 O(n)이다.

2)Search : O(n)

  • Access와 같은 이유겠쥐?
  • 원하는 값을 조회하려면 head부터 찾아야하니깐,,,또 최대 n번일 움직일 수가 있는것이지...

3)Insertion : O(n), O(1)

  • 노드를 중간에 추가하는 경우의 시간 복잡도는 O(n)이다.
  • 맨 앞, 혹은 맨 뒤에 추가하는 경우의 시간 복잡도는 O(1)이다.
  • 세번째 그림은 tail 뒤에 바로 추가하는 것이라고 생각하면 된다.

4)Deletion : O(n), O(1)

  • Insertion과 마찬가지로 삭제하는 경우의 시간 복잡도도 O(n)이다.
  • 맨 앞, 맨 뒤 삭제는 당연 O(1)이 겄지?
  • 아래 그림은 tail 노드를 삭제하고, 이전의 노드를 tail이라고 설정하면 된다. (어렵게 생각ㄴㄴ)

5. 구현 코드

  • 구현은 단일연결리스트로 구현했다.
  • addToTail(insertion)은 tail뒤에 추가하는 방법으로 구현했다.
  • 함수의 재사용성을 높이기 위해서 remove를 구현할 때 indexOf와 getNodeAt을 통해 구현했는데, 그렇게 구현하면 시간 복잡도가 증가할 것 같다. 수정이 필요하다.
    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);
        if (this.head === null) {
          this.head = node;
          this.tail = node;
        }
        else {
          this.tail.next = node;
          this.tail = node;
        }
      }
      remove(value) {
        let currNodeIdx = this.indexOf(value);
        let currNode = this.getNodeAt(currNodeIdx);
        let prevNodeIdx = currNodeIdx - 1;
        let prevNode = this.getNodeAt(prevNodeIdx);
        if (currNode === this.head) {
          this.head = currNode.next;
        }
        else {
          prevNode.next = currNode.next;
        }
        currNode.next = null;
        this.tail = this.getNodeAt(this.size() - 1);
      }
      // index 위치에 노드를 출력한다.
      getNodeAt(index) {
        let tmp = this.head;
        for (let i = 0; i < index; i++) {
          if (tmp === null) {
            return undefined;
          }
          tmp = tmp.next;
        }
        return tmp;
      }
      // 매개변수 value와 같은 값을 지닌 node가 있는지 확인한다.
      contains(value) {
        if (this.indexOf(value) === -1) {
          return false;
        }
        else {
          return true;
        }
      }
      // indexOf
      indexOf(value) {
        let tmp = this.head;
        let count = 0;
        while (tmp !== null) {
          if (tmp.value === value) {
            return count;
          }
          count++;
          tmp = tmp.next;
        }
        return -1;
      }
      size() {
        let tmp = this.head;
        let length = 0;
        while (tmp !== null) {
          length++;
          tmp = tmp.next;
        }
        return length;
      }
    }

2. Hash Table


1. hash table이란?

  • 해시 테이블은 연관배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조이다.
  • 쉽게 말해서 key입력하면 value 나오게 하는 1대1 매칭 시킨 자료구조인데, key를 해시함수를 통해서 배열의 index로 바꿔버리고 그 index로 value를 배열에 저장시켜 놓는 형태임
  • 이해안되면 밑에 그림 ㄱㄱ

2. hash table 구조

  • key : 고유한 값이며, 해시 함수의 input이 된다.

  • hash function : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.

  • hash : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket)의 index이다.

  • value : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

3. hash table 시간 복잡도(Time Complexity)

  • 해시테이블의 시간복잡도는 충돌이 났을때와 나지 않았을때를 나누어 생각할 수 있다.

  • input으로 들어가는 keys의 hash(bucket의 인덱스)가 전부 다를 경우 삽입, 삭제, 조회가 한번에 가능하다.

  • 위에 그림처럼 buckets의 152번에서 John Smith와 Sandra Dee의 hash가 겹쳐 충돌이 일어나면, 처음 들어간 value의 뒷 노드로 다음 value를 저장한다. (buckets에 연결리스트를 사용한거임)

  • 정리하자면 충돌이 일어나면 -> 리스트로 value를 저장하고 -> key와 매치되는 value를 삽입, 삭제, 조회할 때 리스트를 순회하기 때문에 최대 n번의 작업을 하게 될 수 있음.

  • 충돌이 나지 않았을 경우

    1) Insertion : O(1)

    2) Deletion : O(1)

    3) Search : O(1)

  • 충돌이 생겼을 경우

    1) Insertion : O(n)

    2) Deletion : O(n)

    3) Search : O(n)


4. 구현 코드

  • Open Addressing, Chaining 등 충돌을 해결하기 위한 기법이 있지만, 자바스크립트는 객체라는 자료형이 있기 때문에 buckets으로 객체를 사용했다.
  • 하지만 원래의 hash table 정의와 구조라면 객체를 사용하지 않고 다르게 구현해 봐야할 것 같다.
    class HashTable {
      constructor() {
        this._size = 0;    // size = input의 개수 , storage의 크기를 나타내는 변수가 아니다.
        this._limit = 8;
        this._storage = LimitedArray(this._limit);
      }
      insert(key, value) {
        const index = hashFunction(key, this._limit);
        let hasValue = this._storage.get(index);
        let obj = hasValue ? hasValue : {}
        obj[key] = value;
        this._storage.set(index, obj)
        this._size++;
        if (this._size > this._limit * 0.75) {
          this._resize(this._limit * 2);
        }
      }
      retrieve(key) {
        const index = hashFunction(key, this._limit);
        if (this._storage.get(index) && this._storage.get(index)[key]) {
          return this._storage.get(index)[key];
        }
        else {
          return undefined;
        }
      }
      remove(key) {
        const index = hashFunction(key, this._limit);
        delete this._storage.get(index)[key];
        if (this._size < this._limit * 0.25) {
          this._resize(this._limit / 2);
        }
        this._size--;
      }
      _resize(newLimit) {
        const originStorage = this._storage;
        this._limit = newLimit;
        this._storage = LimitedArray(this._limit);
        this._size = 0;
        // originStorage가 each 내부의 this로 바인딩 되지 않게 하기 위해서, 화살표 함수를 사용한다.
        originStorage.each(obj => {
          for (let key in obj) {
            this.insert(key, obj[key])
          }
        });
      }
    }


3. 정리


1. 이중연결리스트, 원형연결리스트도 구현해보자.

2. 자료구조 구현시 시간복잡도에 유념하면서 구현하자.

3. 자료구조 구현시 시간복잡도에 유념하면서 구현하자.

4. 해시테이블의 buckets을 객체를 사용하지 않고 구현해보자.

5. 해시의 충돌을 해결하기 위한 방법으로 chaining과 open address를 구현해보자.


# Work Off


흐물흐물....그래도 생각보다 할만하네...ㅎㅎ😭

기본기가 탄탄한 풀스택 개발자가 되는 그날까지 🔥🔥🔥

profile
Communication : any

0개의 댓글