TIL [자료 구조 - Linked List & Hash Table]

dlrbwls0302·2021년 1월 22일
0

연결 리스트 (Linked List)의 개념

연결 리스트는 크기가 동적인 자료 구조이고 자료 구조를 구성하는 요소를 노드(node)라고 부른다. 노드는 아래 그림처럼 데이터와 다음 노드를 가리키는 주소로 이루어져 있다.


연결 리스트와 배열의 차이점 (중요)

1. 배열의 장점

배열은 접근이 빠르다는 장점이 있다. 만약 n번째 인덱스의 요소에 접근할 경우 arr[n]을 사용하면 바로 접근할 수 있다는 점이다. 실제로 time complexity(시간 복잡성)를 보면 배열에서 원소를 접근할 때는 O(1)만큼의 시간이 걸린다.

2. 배열의 단점

배열(자바스크립트의 배열x)은 처음에 만들때 크기를 선언해야 하고 이는 수정할 수 없기 때문에 안쓰는 메모리 공간 생기는 경우가 있다. 즉, 메모리 사용에 있어서 연결 리스트보다 비효율적이라고 할 수 있다.

3. 연결 리스트의 장점

배열처럼 처음 선언할 때 크기를 정하고 시작하는게 아니라 필요할 때 마다 노드를 생성해서 원하는 곳에 붙여주기만 하면 된다. 따라서 메모리 공간 사용이 효율적이고, 내가 노드를 추가하고 싶은 위치를 이미 알고있다는 기준 하에(보통은 내가 추가하려는 위치의 전의 노드를 알고 있다) 걸리는 시간은 O(1)이다. 노드의 삭제도 마찬가지이다. 내가 삭제하려는 노드의 위치를 알 경우, 예를 들어 가장 앞부분(head)을 삭제할 경우 걸리는 시간은 O(1)이다. 하지만 중간 부분을 삭제하려면 노드의 특성(다음 노드의 위치는 알지만 앞에 노드의 위치는 모름)상 처음부터 하나씩 훑어가면서 찾아야하기 때문에 O(n)이 걸린다.

4. 연결 리스트의 단점

이렇게 빠른 추가와 삭제에 대한 대가로 연결 리스트는 배열과는 다르게 인덱스를 가지고 있지 않다. 따라서 특정한 노드에 접근이나 찾으려고 할 때는 처음부터 훑어야 하는 번거로움이 있고 걸리는 시간 또한 O(n)이 걸린다.


연결 리스트의 종류

1. 단일 연결 리스트 (Single-Linked List)

단일 연결 리스트의 노드는 데이터와 다음 노드를 가리키는 주소로 이루어져 있다. 다음 주소밖에 모르기 때문에 특정한 노드를 한 번 지나쳐 버리고나면 다시 찾을땐 처음(head)부터 찾아야 하는 번거로움이 있다.

2. 이중 연결 리스트 (Doubly-Linked List)

단일 연결 리스트와는 다르게 각 노드에는 데이터와 다음 노드를 가리키는 주소 뿐만 아니라 전의 노드를 가리키는 주소도 있기 때문에 노드의 삽입이나 삭제가 무조건 O(1)만큼의 시간밖에 걸리지 않는다. 나(삭제하려는 노드)는 전의 노드의 주소도 알고 있고, 다음 노드의 주소도 알기 때문에 전의 노드의 다음 주소로 나의 다음 노드를 선택하고 나의 다음 노드도 나의 전의 노드를 전의 노드로 설정해 주면 된다. 그럼 가비지 콜렉터에 의해 나는 사라지게 된다.


해시 테이블 (Hash Table)

해시 테이블은 한 쌍의 키와 값을 해시 테이블이라는 특별한 저장 공간에 저장하는 자료 구조를 뜻한다. 키를 해시 함수에 넣으면 특정한 숫자를 반환하는데 이게 바로 해시 테이블안에서 주소가 된다. 예를 들어 해시 테이블이 호텔이고 해시 함수를 호텔 프런트라고 하자. 손님이 호텔 프런트(해시 함수)에 가서 몇 번 방인지 배정을 받는다. 그 배정에 따라서 손님이 쓰게될 방이 달라진다.

해시 테이블은 가져오고, 추가하고, 삭제하는 모든 것이 O(1)이다. 키만 알고 있다면 데이터를 가져오고, 추가하고, 삭제하는 것이 아주 빠르고 간편한다. 하지만 한 가지 주의 사항은 만약 **해시 충돌(Hash Collision)**이 일어날 최악의 경우 bucket안의 모든 key를 찾아봐야 할 수도 있기 때문에 O(n)이 걸릴 수 도 있다. 따라서 가져오고, 추가 , 삭제가 O(1)이 될 수도 있고 O(n)이 될 수도 있다.


해시 충돌 해결 법 두 가지 - 분리 연결법, 개방 주소법

1. 분리 연결법 (Seperate Chaining or Chaining)

John Smith라는 키를 해시 함수에 넣었더니 152라는 숫자 값을 얻었는데 Sandra Dee라는 키도 해시 함수에 넣었더니 152라는 숫자 값이 나온 것을 알 수 있다. 152라는 한 주소에 두 개의 값이 할당 되려하니 해시 충돌이 발생했다. 이럴 때 해시 충돌을 해결할 방법 중 하나인 분리 연결 법을 쓰면 같은 주소에 연결 리스트 처럼 데이터를 넣어주게 된다. 152라는 주소에 먼저 John Smith라는 키와 521-1234라는 값이 저장되었고 그 다음 노드로 Sandra Dee라는 키와 521-9655라는 값을 저장해 주었다. 체이닝 방식의 장점은 해시 테이블의 확장이 필요없고 간단하게 구현할 수 있으며 손쉽게 삭제할 수 있다는 점이다.

2. 개방 주소법 (Open Addressing)

개방 주소법은 분리 연결법과는 달리 비어있는 해시를 찾아서 데이터를 저장한다. 만약 위에 그림처럼 152라는 주소에 John Smith라는 키와 521-1234라는 값이 저장되어 있는데 Sandra Dee라는 키도 152라는 주소 값을 얻은 것을 확인할 수 있다. 개방 주소법의 경우 이럴 때 Sandra Dee는 다른 비어있는 주소에 저장되게 된다. 이때 중요한 점은 비어있는 해시를 찾는 과정은 일정해야 한다는 것이다. 비어있는 해시를 찾는 과정은 다음과 같다.

  1. 선형 탐색 (Linear Probing)
    해시 함수에서 얻어낸 주소에 이미 다른 데이터가 있는 경우, 그 주소에서 고정된 폭만큼 다른 주소로 이동하는 방식이다.

  2. 제곱 탐색 (Quadratic Probing)
    선형 탐사는 고정된 폭만큼 다른 주소로 이동한다면 제곱 탐색은 이동 폭이 제곱만큼 크다.

  3. 이중 해시 (Double Hashing)
    2개의 해시 함수를 이용해 첫 번째 해시 함수에서 나온 값이 해시 충돌을 일으킬 경우, 두 번째 해시 함수를 이용해서 나온 값에 저장하는 방식이다.

profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글