일반 배열과, 링크드 리스트를 비교해 주세요.
데이터를 순차적으로 저장한다는 공통점이 있지만, 메모리 구조와 연산 성능에서 근본적인 차이가 있습니다.
메모리 구조 비교
배열 (연속된 메모리)
[10][20][30][40][50]
↑ 주소가 연속적 → 인덱스로 바로 접근 가능
링크드 리스트 (불연속 메모리)
[10|*] → [20|*] → [30|*] → null
↑ 각 노드가 흩어져 있고 포인터로 연결
시간복잡도 비교
| 연산 | 배열 | LinkedList |
|---|---|---|
| 인덱스 접근 | O(1) O | O(n) |
| 맨 앞 삽입/삭제 | O(n) | O(1) O |
| 맨 뒤 삽입/삭제 | O(1) | O(n) / O(1)* |
| 중간 삽입/삭제 | O(n) | O(n) 탐색 + O(1) |
| 탐색 | O(n) | O(n) |
*이중 연결 리스트(tail 포인터 보유)의 경우 O(1)
특성 비교
| 항목 | 배열 | 링크드 리스트 |
|---|---|---|
| 메모리 공간 | 연속 필요 | 불연속 가능 |
| 크기 | 고정 (정적) | 동적 확장 |
| 추가 메모리 | 없음 | 포인터 저장 비용 |
| 캐시 효율 | 높음 O | 낮음 |
캐시 효율 차이
배열: 연속 메모리 → CPU 캐시에 한번에 올라옴 → 빠름
링크드 리스트: 노드가 흩어짐 → 매번 캐시 미스 발생 → 느림
이론상 중간 삽입은 링크드 리스트가 유리하지만, 캐시 효율 때문에 실제 성능은 배열이 더 빠른 경우가 많습니다.
언제 무엇을 쓸까?
| 상황 | 선택 |
|---|---|
| 인덱스 접근이 빈번 | 배열 O |
| 크기가 고정적 | 배열 O |
| 맨 앞 삽입/삭제가 빈번 | 링크드 리스트 O |
| 크기가 예측 불가 | 링크드 리스트 O |
| 일반적인 상황 | 배열(ArrayList) O |