토픽 69 / 76·비교표
## Part 2: 선형 자료구조
배열 vs 연결 리스트
| 항목 | 배열 | 연결 리스트 |
|---|
| 메모리 | 연속 공간 | 비연속 (포인터 연결) |
| 크기 | 고정 (동적 배열 제외) | 동적 |
| 접근 | O(1) 임의 접근 | O(n) 순차 접근 |
| 삽입/삭제 | O(n) 중간 | O(1) 위치 알 때 |
| 캐시 | 친화적 (연속 메모리) | 비효율 (분산 메모리) |
| 적용 | 룩업 테이블, 행렬 | LRU 캐시, 해시 체이닝 |
동적 배열 vs 연결 리스트
| 항목 | 동적 배열 | 연결 리스트 |
|---|
| 메모리 | 연속 (재할당 시 복사) | 비연속 |
| 접근 | O(1) | O(n) |
| 끝 추가 | O(1) 분할상환 | O(1) (tail 유지 시) |
| 중간 삽입 | O(n) | O(1) (위치 알 때) |
| 적용 | ArrayList, vector | 동적 크기 필요 시 |
단일 vs 이중 vs 원형 연결 리스트
| 항목 | 단일 | 이중 | 원형 |
|---|
| 포인터 | next만 | prev + next | next (마지막→첫번째) |
| 탐색 | 단방향 | 양방향 | 무한 순환 |
| 삭제 | O(n) (이전 노드 탐색) | O(1) (prev 직접) | O(n) |
| 메모리 | 가장 적음 | 2배 포인터 | 단일과 유사 |
| 적용 | 기본 리스트 | LRU 캐시, Undo/Redo | 라운드 로빈, 게임 턴 |
스택 vs 큐
| 항목 | 스택 | 큐 |
|---|
| 원칙 | LIFO (후입선출) | FIFO (선입선출) |
| 접근 | top만 | front/rear |
| 연산 | push/pop O(1) | enqueue/dequeue O(1) |
| 적용 | DFS, 함수 호출, Undo | BFS, 프로세스 스케줄링 |
| 구현 | 배열/연결리스트 | 원형 큐/연결리스트 |
덱 vs 큐 vs 스택
| 항목 | 덱 (Deque) | 큐 | 스택 |
|---|
| 삽입 | 양쪽 | rear만 | top만 |
| 삭제 | 양쪽 | front만 | top만 |
| 유연성 | 최고 (양방향) | FIFO | LIFO |
| 적용 | 슬라이딩 윈도우 | 순차 처리 | 역순 처리 |
우선순위 큐 vs 일반 큐
| 항목 | 우선순위 큐 | 일반 큐 |
|---|
| 순서 | 우선순위 기반 | FIFO (삽입 순서) |
| 구현 | 힙 기반 | 배열/연결리스트 |
| 삽입 | O(log n) | O(1) |
| 삭제 | O(log n) | O(1) |
| 적용 | Dijkstra, 작업 스케줄링 | BFS, 버퍼 |