최근 알고리즘 문제를 풀면서 기본기가 많이 부족하다는 걸 몸소 느끼는 중인데,
그중 하나가 자료구조!
매일 쓰는 List (그것도 ArrayList 만) 와 Map (그것도 HashMap 만) 말고는 전혀 사용하지 않았는데...
알고리즘 문제 풀이에서 훨~ 씬 쉽게 풀 수 있는 걸 저 두 개로만 풀어내려고 하니까 어렵기도 하고 비효율적이기도 하고
그래서 자료구조를 정리해 보려고 한다
1. List 리스트
순서가 있는 중복 가능한 컬렉션
요소들이 인덱스로 접근할 수 있기 때문에 순서가 중요한 데이터를 다룰 때 유용하다.
대표 구현체
| 종류 | 설명 |
| ArrayList | 동적 배열 기반, 인덱스 접근이 빠르지만 삽입 및 삭제가 비교적 느리다 |
| LinkedList | 연결 리스트 기반, 삽입 및 삭제가 빠르지만 인덱스 접근이 비교적 느리다 |
2. Set 셋
중복을 허용하지 않는 컬렉션
대표 구현체
| 종류 | 설명 |
| HashSet | 해시 테이블을 사용하여 데이터를 저장하고, 순서가 보장되지 않지만 검색 성능이 좋다 |
| TreeSet | 이진 탐색 트리 기반으로 구현되어 있고, 오름차순 또는 내림차순 순서를 보장한다 |
3. Map 맵
키-값 쌍으로 데이터를 저장하는 컬렉션
키는 중복될 수 없고, 값은 중복될 수 있다.
대표 구현체
| 종류 | 설명 |
| HashMap | 해시 테이블을 사용하여 데이터를 저장하고, 순서가 보장되지 않는다 |
| TreeMap | 이진 탐색 트리 기반으로 구현되어 있고, 키를 기준으로 오름차순 정렬된다 |
4. Stack 스택
후입선출(LIFO) 구조의 컬렉션
삽입과 삭제가 한쪽 (주로 스택의 상단) 에서만 일어난다.
뒤에서부터 데이터를 처리해야 할 때 유용하다.
대표 구현체
| 종류 | 설명 |
| Stack | 최근에는 잘 사용하지 않는다 |
| Deque | 스택을 구현할 수 있는 인터페이스이다 |
5. Queue 큐
선입선출(FIFO) 구조의 컬렉션
삽입과 삭제가 양쪽 끝 (주로 큐의 앞부분에서 삭제, 뒷부분에서 삽입) 에서 일어난다.
순차적으로 데이터를 처리해야 할 때 유용하다
대표 구현체
| 종류 | 설명 |
| LinkedList | 큐의 구현체로 사용할 수 있는 LinkedList 클래스이다 |
| PriorityQueue | 유선순위 큐로, 기본값인 오름차순으로 처리된다 |
요약
| 종류 | 순서 | 중복 | 특징 |
| List | O | O | |
| Set | 구현체에 따라 다름 | X | |
| Map | 구현체에 따라 다름 | 키는 불가, 값은 가능 | 키-값 |
| Stack | O | O | LIFO |
| Queue | O | O | FIFO |