큐(Queue)
- 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조
우선순위 큐(Priority Queue)
- 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조
- 오름차순이 기준이면 값이 작은 값이 1순위로 출력
- 내림차순이 기준이면 값이 높은 값이 1순위로 출력
- 일반적으로 힙 기반 구현 -> 완전 이진트리 구조 -> 힙 트리의 높이 log(n+1), 시간 복잡도 O(logn)
- 배열 또는 연결리스트를 이용하여 구현 가능 -> 선형 구조의 자료구조 -> 삽입 or 삭제 연산 시간복잡도 O(n)
힙 구현
- 완전 이진트리 -> 중간에 비어있는 요소가 없기 때문
- 배열로 구현하였기 때문에 부모, 자식 노드 찾기 수월
자식 노드 구하기
- 왼쪽 자식 노드 index = (부모 노드 index) * 2
- 오른쪽 자식 노드 index = (부모 노드 index) * 2 + 1
부모 노드 구하기
- 부모 노드 index = (자식 노드 index) / 2
우선순위 큐 삽입 연산
1. 완전 이진트리의 마지막 노드에 이어 새로운 노드 추가
2. 추가된 새로운 노드를 부모의 노드와 비교 및 교환
3. 정상 힙트리가 될 때까지 2. 반복
- 최악의 경우, 새로 추가된 노드가 루트 노드까지 비교하며 올라감 -> 시간복잡도 O(logN)
우선순위 큐 삭제 연산
1. 루트 노드 삭제
2. 삭제된 노드자리에 마지막 노드 이동
3. 루트 자리의 노드가 자식 노드와 비교하며 교환(최대힙은 큰 값과 교환, 최소힙은 작은 값과 교환)
4. 정상 힙트리가 될 때까지 3. 반복
- 최악의 경우 루트 노드부터 마지막 노드까지 이동 -> 시간복잡도O(logN)
맵(Map)
- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
- 레드 블랙 트리 자료구조를 기반으로 형성
- 삽입하면 자동으로 정렬
- Map<String, Integer> 의 형태
- key의 중복 허용하지 않음
- 순서보다는 정의된 이름(key)와 상응하는 데이터들을 묶기 위한 자료구조
Map 자료구조의 대표적인 종류
1. HashMap
- key와 value의 쌍으로만 구성이 될뿐 자료구조 안에 묶인 쌍들에 대한 순서를 보장할 수 없음
- 즉, 사용자는 키와 값이 구성되는 위치를 결정하거나 알 수 없음
- 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능
2. TreeMap
- 이진트리 기반 Map
- key의 값을 이용해 순서대로 정렬하여 데이터를 저장하는 자료구조
- 데이터 저장 즉시 정렬하기 때문에 추가 or 삭제 기능은 HashMap 보다는 오래걸림
- 정렬 상태 유지해야하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우, 효율적
- 이진탐색 트리는 트리의 높이만큼 시간 필요 -> 데이터가 한쪽으로 편향된 경우, 비효율
- 레드블랙 트리로 이진탐색 트리의 문제점 보완 -> 부모 노드보다 작은 값 노드는 왼쪽, 반대는 오른쪽으로 배치하여, 데이터의 추가나 삭제 시 트리가 균형을 유지하도록 함
3. LinkedHashMap
- 데이터를 입력한 순서대로 쌓아지며 데이터를 저장하는 자료구조
- 배열, 리스트처럼 인덱싱 접근을 하기에 용의
셋(Set)
- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
- 중복되는 요소는 없고, 오로지 희소한 값만 저장하는 자료 구조
- 해시 테이블을 사용해서 해시값 기반 데이터를 저장 -> 특정값을 포함하는지 확인하는 작업 매우 빠름
해시 테이블(Hash table)
- 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
- 내부적으로 배열(버킷)을 사용하여 데이터를 저장 -> 빠른 검색 가능
- 삽입, 삭제, 탐색 시 평균 O(1)의 시간 복잡도를 가짐