Data Structure Ⅱ - Linked List & Hash Table

future·2021년 1월 21일

목록 보기

8/10

📎 Linked List (연결 리스트)

🏷️ Linked List와 노드

연결 리스트(Linked List)는 노드라고 불리는 요소들을 링크를 통해 연결하는 자료구조이다. 노드는 데이터와 링크로 구성되어 있는데, 데이터를 저장하는 장소와 다른 노드를 가리키기 위한 장소가 구분되어 있다는 것을 알 수 있다. 여기서 링크는 포인터라는 개념으로 불리기도 하는데, 이 포인터를 통해 데이터를 추가하거나, 삭제하거나 혹은 탐색할 수 있다.

연결 리스트에서는 가장 첫 노드를 head, 가장 마지막 노드를 tail이라고 한다. 각 노드가 가지고 있는 포인터를 통해 노드의 연결을 알 수 있으며, 이를 통해 각 노드는 본인 이전 노드와 다음 노드를 기억한다. 만약 다음 노드의 포인터가 null을 가리킬 경우에는 리스트의 끝에 도달했음을 알 수 있다.

우리가 흔히 컴퓨터에서 사용하는 실행취소/실행복구가 연결 리스트의 예시라고 볼 수 있겠다. 어떤 작업을 수행할 때, 이전 실행으로 되돌리고 싶을 경우 우리는 단축키 ctrl+z를 사용한다. 이 단축키를 통해 계속해서 실행취소를 하다 보면 가장 초기 작업이었던 head에 도달하게 될 것이다. 반대로 단축키 ctrl+y를 통해 가장 최근 작업으로 실행복구를 하다보면 가장 마지막에 작업한 tail까지 갈 수 있다.

🏷️ Linked List 종류

단일 연결 리스트 (Singly-Linked List)

단일 연결 리스트에서는 노드가 다음 노드에만 연결되어 있다. 그러므로 이전 노드는 확인이 불가능하다. 만약 포인터가 null을 가리킨다면 그 리스트는 끝에 도달했다고 할 수 있다.

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

이중 연결 리스트에서 각 노드는 포인터를 두 개 가지고 있는데, 각 포인터들은 이전 노드와 다음 노드를 가리키기 때문에 이전 노드와 다음 노드에 대한 확인이 둘 다 가능하다. 여기서 head와 tail 노드는 제외된다.

🏷️ Linked List의 주요 속성

addToTail() : 주어진 데이터를 리스트의 끝에 추가
remove() : 주어진 데이터를 찾아서 연결을 삭제
getNodeAt() : 주어진 인덱스의 노드를 찾아서 반환
contains() : 리스트에 주어진 데이터를 가진 노드의 존재 여부를 반환
indexOf() : 주어진 데이터의 인덱스를 반환

🏷️ 배열과 Linked List의 차이점

배열은 요소들이 각각 순서를 가지면서 들어오지만, Linked List는 노드가 바로 이전 요소나 다음 요소 옆에 들어가지는 않는다. 그래서 배열에 비해 데이터의 추가나 삭제가 용이하여 더 효율적이라는 장점이 있다. 반면, 데이터를 탐색하고 정렬하기 위해서는 처음부터 끝까지 순회하기 때문에 느리다는 단점이 있다.

📎 Hash Table

🏷️ 해싱(Hashing)이란?

해싱이란 데이터를 더욱 빠르게 저장하고 꺼낼 수 있도록 특정 데이터(key)를 고정된 형식의 데이터(index)로 변환하여 bucket에 연결하는 것이다. 해시 테이블은 key를 저장할 때 메모리 공간을 덜 사용하기 위해 해시 함수를 이용하여 key를 특정 index로 변환시켜 준다. 해시 테이블에서는 데이터를 key-value 쌍으로 저장하며, 데이터를 식별하는 데에 사용되는 key는 해시함수의 인자로 전달된다.

🏷️ 해시 함수의 특징

어떠한 입력값에도 항상 고정된 길이의 해시값을 출력한다.
입력값의 일부만 변경되어도 아예 다른 결과값을 출력한다.
출력된 결과값을 바탕으로 입력값을 유추할 수 없다.

🏷️ 해시 충돌과 해결 방법

만약 해시함수가 서로 다른 key(입력값)에 대해 동일한 index(출력값)을 만들어낸다면? 데이터가 들어갈 수 있는 공간은 한 개인데 들어가야 하는 데이터는 두 개가 되는 난감한 상황, 즉 해시 충돌(Hash Collision)이 발생한다. 이런 상황을 피하기 위해 해시함수는 해시 충돌이 되도록 발생하지 않도록 잘 구성되어야 하지만, 아무리 해시함수를 잘 구현한다고 하여도 완벽하게 충돌을 막기에는 어려움이 있다.

그렇다면 해시 충돌을 어떻게 해결할까? 해시 충돌 해결 방법에는 크게 두 가지가 있다.

1. 체이닝 (chaining)
bucket 안에 연결 리스트를 할당하여 해시 충돌 발생 시 연결 리스트로 데이터들을 연결하는 방법이다. 같은 index로 해싱되는 데이터를 하나의 연결 리스트로 관리한다. 연결 리스트만 사용하면 되기 때문에 따로 복잡하게 계산식을 사용할 필요가 적다.

2. 개방 주소법 (Open Addressing)
해시 충돌이 일어날 경우 다른 bucket에 데이터를 삽입하는 방식이다. 체이닝처럼 포인터가 필요 없고, 지정한 메모리 외 추가적인 저장공간이 필요없다는 것이 장점이다. 개방주소법은 저장할 데이터가 적을 시 더 유리하다는 특징이 있다.