배열·연결 작업 부하 구현 선택표
실제 구현을 선택할 때 List 구현 선택은 단일 연산 표가 아니라 애플리케이션의 연산 혼합을 입력으로 합니다. Java LinkedList는 양방향 링크와 first·last를 유지해 메모리 비용도 더 큽니다. 일반적인 기본값은 ArrayList이고 반대 증거가 있을 때 교체합니다.
| 질문 | 관찰 | 결정 |
|---|---|---|
| 임의 조회 비율은 얼마인가 | get(index) 횟수 | 배열 가중 |
| 앞 변경 비율은 얼마인가 | index 0 변경 | 연결 가중 |
| 순차 순회가 중심인가 | 전체 스캔 횟수 | 캐시 효과 측정 |
| 위치 참조를 이미 갖는가 | Node 핸들 보유 | 연결 O(1) 인정 |
핵심: 배열·연결 작업 부하은 Big-O의 전제를 코드 경로와 연결합니다. 마지막 절에서는 Java ArrayList·LinkedList의 실제 계약과 연습 문제를 묶어 선택 규칙을 완성합니다.