배열과 연결 목록 비용은 작업별 실제 동작으로 비교한다
Big-O와 함께 원소 이동·next 추적·연속 메모리·tail 보유라는 전제를 기록합니다.
| 작업 | 배열 | 연결 |
|---|---|---|
| get(index) | 주소 계산 O(1) | next 추적 O(n) |
| 앞 삽입 | n칸 이동 | head 교체 O(1) |
| 끝 추가 | 여유 시 O(1) | tail 있으면 O(1) |
| 전체 순회 | 연속·캐시 우호 | Node 분산 |
핵심: 같은 입력 크기와 위치, 같은 최종 결과를 사용해야 비교가 의미 있습니다.
Big-O와 함께 원소 이동·next 추적·연속 메모리·tail 보유라는 전제를 기록합니다.
| 작업 | 배열 | 연결 |
|---|---|---|
| get(index) | 주소 계산 O(1) | next 추적 O(n) |
| 앞 삽입 | n칸 이동 | head 교체 O(1) |
| 끝 추가 | 여유 시 O(1) | tail 있으면 O(1) |
| 전체 순회 | 연속·캐시 우호 | Node 분산 |
핵심: 같은 입력 크기와 위치, 같은 최종 결과를 사용해야 비교가 의미 있습니다.