IM 6일차 초보개발자 TIL(Linked list & Hash table)

DATA 구조에서 linked list 와 hash table에 대해서 배우는 날이었다,

 

stack과 queue에 비해서는 조금 더 복잡한 형태의 DATA구조 였다.

 

---

 

Linked list

 

linked list(연결 리스트)는 각 노드(Node)가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 DATA구조이다.

 

데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다.

 

위 그림과 같이 노드는 자기자신을 가리키는 원소와 다음 노드를 가리키는 포인터로 구성되어 있다.

 

연속되는 노드들은 포인터로 연결되어 있으며, 마지막 항목은 Null을 가리킨다.

 

또한, 프로그램이 수행하는 동안 크기가 커지거나 작아질 수 있으며, 메모리 공간을 낭비하지는 않는다.

 

 

liked list 장점

 

연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다.

 

liked list 단점

 

배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다.

 

 

liked list의 종류

 

단일 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

 

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

 

이중 연결 리스트의 구조는 단일 연결 리스트와 비슷하지만,

 

포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다.

 

---

 

 

 

 

 

Hash table

 

hash table(해시 테이블)은 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열에추가에 사용되는 DATA구조이다.

 

hash table은 해시 함수라는 함수를 사용하여 index를 bucket이나 slot의 배열로 계산한다.

 

hash table 장점

 

해당 키와 배열의 index를 가지고 있기 때문에 삽입, 검색, 삭제가 용이하다.

 

hash table은 메모리 공간을 덜 사용할 수 있게 만들어지고, 필요할 때에만 메모리 크기를 늘리는 특징이 있다.

 

hash table 단점

 

hash table 크기가 유한하고 , 해시 함수의 특성으로 hash 충돌이 일어날 수 있다.

 

hashing과 해시 충돌

 

hash table을 통한 탐색을 hashing 이라고 하며, 키 값에 직접 산술적인 연산을 통해 테이블 주소를 계산하여 항목에 접속한다.

hashing을 하다보면 똑같은 index를 받게 되는데, 이때 충돌(collision)이 발생한다.

 

hash 충돌을 해결하기 위해서는 hash table에 linked list 형식으로 연결해주면 된다.

 

---

stack & queue에 비해서 linked list 와  hash table은 구조를 이해하고 구현하는데 어려움이 많았다.

 

작동되는 원리가 좀더 복잡하다 보니 이해하는데도 오래걸렸다.

 

자바스크립트로 구현하면서 다시한번 DATA구조에 대한 공부를 복습해야할 것 같다.