덱 (Deque, Double-Ended Queue)
: 양쪽(앞과 뒤)에서 데이터를 넣고 뺄 수 있는 자료구조
- 데이터의 삽입과 제거를 head와 tail 두 군데서 자유롭게 할 수 있는 자료구조
- 스택(Stack) + 큐(Queue)
- 스택: head에서 데이터 삽입, 제거
- 큐: head에서 데이터 삽입, tail에서 제거
- 덱을 이용하면 스택과 큐를 전부 구현할 수 있음
덱의 추상 자료형
| printAll() | 리스트의 모든 요소 출력 |
| addFirst() | 리스트의 head에 데이터 삽입 |
| removeFirst() | 리스트의 head에서 데이터 제거 |
| addLast() | 리스트의 tail에 데이터 삽입 |
| removeLast() | 리스트의 tail에서 데이터 제거 |
| isEmpty() | 리스트가 비었는지 확인 |
해시 테이블 (Hash Table)
: 키(Key)를 해시 함수로 변환해서 값을 빠르게 저장하고 찾는 자료구조
- 해시(Hash), 맵(Map), 해시맵(Hash Map), 딕셔너리(Dictionary)라고도 불림
- 해시(Hash) + 테이블(Table)이 합쳐진 자료구조
- 해시 함수
: 어떤 키(Key)를 입력하면, 고정된 크기의 숫자(주소)로 바꿔주는 함수- ex) “apple” → 42
- 테이블(Table)
: 데이터를 저장하는 배열 같은 공간(표)
- 해시 함수
특징
- 키(Key)만 알면 Value 값을 O(1)의 성능으로 읽을 수 있음
- 삽입, 수정, 삭제도 O(1)의 성능을 가짐
- 해시 함수 선정이 매우 중요함
- 좋은 해시 함수: 데이터를 골고루 분배시켜주는 함수
해시 테이블의 문제점
충돌(Conflict) 발생
- 충돌: 서로 다른 키가 해시 함수를 거쳤는데, 같은 위치(주소)에 저장되려고 하는 일
- ex) 사물함을 민수도 3번, 지수도 3번 사물함에 배정됨
충돌 해결 방법
- 충돌한 인덱스를 연결 리스트로 구성해서 데이터들을 연결함
⇒ 기존의 value와 새로 들어온 value를 같은 인덱스에 저장할 수 있음 - 예시 흐름
- 새로 들어온 Value의 키를 읽기 요청하면, 해시 함수를 거쳐 배열의 해당 인덱스에 접근
→ 해당 인덱스에는 기존 value와 새 value가 연결 리스트로 저장되어 있음
→ 해당 키의 데이터를 만날 때까지 차례대로 접근 (O(1)의 성능)
- 새로 들어온 Value의 키를 읽기 요청하면, 해시 함수를 거쳐 배열의 해당 인덱스에 접근
해시 테이블의 장단점
장점
- 데이터 읽기, 삽입, 삭제가 빠름
단점
- 메모리를 많이 차지함
- 해시 함수 구현이 매우 중요함 (좋은 해시 함수가 필수)
셋(Set)
: 데이터의 중복을 허용하지 않는 자료구조
- 해시 테이블을 이용해 쉽게 구현 가능
- 해시 테이블의 Value 값은 사용하지 않고, Key만 사용해서 구현
셋의 추상 자료형
| add(data) | 데이터 삽입 → 매개 변수 data가 전달되며, 이 data가 Key이자 데이터 |
| isContain(data) | 셋에 해당 data가 있는지 체크하는 함수 |
| remove(data) | 데이터 제거 → data를 넘겨주면 해당 Key를 해시 테이블에서 제거함 |
| clear() | 셋 비우기 |
| isEmpty() | 셋이 비었는지 확인 |
| printAll() | 셋의 모든 데이터 출력 |