📚 자료구조 정리: 시간복잡도 기준 사용법 (추가/삭제/조회, 앞/중간/뒤)

---

1. 동적 배열 (ArrayList / vector / list)

연산	앞	중간	뒤
추가	❌ O(n)	❌ O(n)	✅ O(1) (amortized)
삭제	❌ O(n)	❌ O(n)	✅ O(1)
조회	✅ O(1)	✅ O(1)	✅ O(1)

특징

• 내부적으로 연속된 메모리 사용
• 중간 삽입/삭제 시 자료 이동이 필요해 비효율적
• 인덱스를 활용한 접근 속도는 빠름

Java 예제

java
복사편집
List<Integer> list = new ArrayList<>();
list.add(10);       // 뒤 추가
list.add(0, 5);     // 앞 삽입
list.get(1);        // 조회
list.remove(0);     // 삭제

---

2. Deque (Double-ended Queue)

연산	앞	중간	뒤
추가	✅ O(1)	❌ 없음	✅ O(1)
삭제	✅ O(1)	❌ 없음	✅ O(1)
조회	✅ O(1)	❌ 없음	✅ O(1)

특징

• 양쪽에서 삽입/삭제 가능
• 스택과 큐 기능을 모두 가짐
• 중간 삽입/삭제는 지원하지 않음

Java 예제

java
복사편집
Deque<Integer> dq = new ArrayDeque<>();
dq.addFirst(10);     // 앞 추가
dq.addLast(20);      // 뒤 추가
dq.removeFirst();    // 앞 제거
dq.removeLast();     // 뒤 제거

---

3. Priority Queue (Heap 기반)

연산	기준	시간복잡도
추가	루트 기준 삽입	✅ O(log n)
삭제	최우선 요소 제거	✅ O(log n)
조회	최우선 요소 확인	✅ O(1)

특징

• 항상 정렬된 우선순위에 따라 요소 유지
• 중간 요소 삽입/삭제 불가
• 내부적으로 힙 구조 사용

Java 예제

java
복사편집
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3); pq.add(1); pq.add(5);
pq.peek();    // 최솟값 조회
pq.poll();    // 최솟값 제거

---

4. HashSet / TreeSet

연산	HashSet (해시 기반)	TreeSet (정렬 트리)
추가	✅ O(1) avg	✅ O(log n)
삭제	✅ O(1) avg	✅ O(log n)
조회	✅ O(1) avg	✅ O(log n)

특징

• 중복을 허용하지 않음
• HashSet: 빠르지만 순서 없음
• TreeSet: 느리지만 자동 정렬

Java 예제 (HashSet)

java
복사편집
Set<Integer> set = new HashSet<>();
set.add(10);
set.contains(10);
set.remove(10);

---

5. HashMap / TreeMap

연산	HashMap (해시 기반)	TreeMap (정렬 트리)
추가	✅ O(1) avg	✅ O(log n)
삭제	✅ O(1) avg	✅ O(log n)
조회	✅ O(1) avg	✅ O(log n)

특징

• (key, value) 쌍 저장
• HashMap은 key 순서 없음, TreeMap은 key 자동 정렬

Java 예제 (HashMap)

java
복사편집
Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.get("apple");
map.containsKey("apple");
map.remove("apple");

---

🧠 자료구조 선택 가이드

자료구조	잘 맞는 상황	피해야 할 상황
ArrayList	인덱스 기반 접근, 뒤에 삽입	앞/중간 삽입/삭제 자주
Deque	양쪽 삽입/삭제 필요	중간 삽입/삭제
PriorityQueue	최댓값/최솟값 정렬 유지	전체 정렬된 리스트 필요
HashSet	빠른 중복 제거, 포함 검사	정렬 필요할 경우
HashMap	빠른 key-based 조회	key 정렬 순회 필요 (→ TreeMap)

---