[D+47] Linked List와 Hash Table

 

D+47

-  Linked List와 Hash Table -

(Linked List, Hash Table)

 

---

 

 

Linked List

•크기가 동적인 자료구조

 

• 노드(데이터 필드 + 링크)의 연결로 이루어진 자료구조

   데이터 필드 - 데이터를 저장하는 곳

   링크 - 다음 노드의 위치를 알려주는 곳

 

 

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

노드 안에 링크가 1개이고, 단방향으로 진행하는 리스트이다.

 

노드 안 링크가 1개이기 때문에 이전 노드로 갈 수 없다.

 

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

노드 안에 링크가 2개 이고 양방향으로 진행할 수 있는 리스트이다.

 

Circular Linked List (환형 연결 리스트)

마지막 노드가 첫 번째 노드를 가리켜서 계속 회전할 수 있게 만들어진 리스트이다.

 

연결 리스트 관련 메서드

•addToTail(value) : 주어진 값을 연결 리스트의 끝에 추가한다.

 

• remove(value) : 주어진 값을 찾아서 연결을 해제(삭제)한다.

 

•getNodeAt(index) : 주어진 인덱스의 노드를 찾아서 반환한다. (값이 아니라 노드를 반환하며 노드가 없을 경우 undefined를 반환한다)

 

•contains(value) : 연결 리스트에 주어진 값을 가지는 노드의 존재 여부를 반환한다.

 

•indexOf(value) : 주어진 값의 인덱스를 반환한다. 없을 경우엔 -1을 반환하다.

 

 

---

Hash Table

•키와 값을 쌍으로 저장하고 있는 자료 구조

 

• 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록 키를 해시함수라는 함수를 통해 특정 숫자 값의 인덱스로 변환한다.

 

•해시 테이블은 필요할 때에만 메모리 크기를 늘리고 가능한 작은 크기를 유지한다.

 

 

해싱 (Hashing)

하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것으로

해싱은 해시 테이블과 해시함수로 구성되어 있다.

 

해시 충돌

해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력 값을 내는 상황

 

해시 테이블 관련 용어

•storage : 해시 테이블에서 자료를 저장하는 전체적인 공간을 나타낸다.

 

• bucket : 각 해시테이블에 인덱스(주소) 별도로 존재하는 슬롯을 의미한다.

 

•tuple : 각각 데이터들을 담고 있는 버킷 내부의 공간을 나타낸다.

 

해시 테이블 관련 메서드

•insert(key, value) : 주어진 키와 값을 저장하며, 이미 해당 키가 저장되어 있다면 값을 덮어 씌운다.

 

•retrieve(key) : 주어진 키에 해당하는 값을 반환하며, 없을 경우 undefined를 반환한다.

 

•remove(key) : 주어진 키에 해당하는 값을 삭제하고 값을 반환하며, 없을 경우 undefined를 반환한다.

 

•_resize(newLimit) : 해시 테이블의 스토리지 배열을 newLiit으로 리사이징하는 함수로, 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 한다.