배열 목록과 연결 목록
조회·앞 삽입·끝 삽입의 이동 또는 링크 추적 횟수를 세어 Big-O와 CPU 캐시 효과를 함께 해석합니다.
ch14-1에서 Big-O를 입력 크기에 따른 작업 증가 모양으로 정의했습니다.
이제 그 기초를 반복하지 않고 배열 목록과 연결 목록의 전제를 같은 표에서 비교합니다.
벽시계 나노초 대신 이동 칸과 next 추적 횟수를 결정적으로 세고, 배열의 연속 접근이 캐시에 유리한 이유도 선택 근거에 포함합니다.
위치 탐색을 제외한 잘못된 비용 계산
중간 Node를 찾는 800번의 next 이동을 빼고 참조 대입 두 번만 셉니다.
결과는 API가 index를 받는 순간 탐색 비용도 전체 연산에 포함해야 함을 보여 줍니다.
public final class LinkedCostAccountingBug {
public static void main(String[] args) {
int index = 800;
int linkWrites = 2;
int reported = linkWrites;
int actualOperations = index + linkWrites;
System.out.println("reported=" + reported + ", actual=" + actualOperations);
}
}reported=2, actual=802복잡도는 마지막 대입만이 아니라 시작부터 결과까지 수행한 일을 셉니다.
이미 Node 참조가 주어진 알고리즘과 index 기반 List API는 전제가 다르므로 같은 표에 섞으면 안 됩니다.
이동·탐색·참조 대입 집계
- 배열
get은 주소 계산으로 접근하지만 연결get은head부터next를 따라갑니다. - 배열 앞 삽입은 기존 원소를 오른쪽으로 이동하고 연결 앞 삽입은
head만 교체합니다. - 꼬리 노드가 있는 연결 목록과 여유 용량이 있는 배열 목록은 끝 추가가 모두 상수 수준입니다.
- 연속 배열 순회는 객체마다 흩어진
Node순회보다 CPU 캐시 지역성이 좋은 경우가 많습니다. - System.arraycopy 같은 최적화된 벌크 복사는 단순 Java 반복보다 상수가 작을 수 있습니다.
- 벤치마크는 워밍업·데이터 크기·연산 분포를 고정하고 결과 변동을 함께 기록해야 합니다.
같은 시나리오를 쓰는 결정적 비용 모델
DeterministicListCostProbe는 같은 중간 인덱스 시나리오에서 탐색과 쓰기를 따로 기록합니다. 실제 시간을 단정하지 않고 연산 수 모델을 출력해 가정을 검토할 수 있게 합니다. 캐시 효과는 별도 측정 항목으로 남깁니다.
public final class DeterministicListCostProbe {
public static void main(String[] args) {
int size = 1_000;
int middle = size / 2;
Cost array = new Cost(middle, size - middle);
Cost linked = new Cost(middle, 2);
System.out.println("array-search=" + array.search() + ", writes=" + array.writes());
System.out.println("linked-search=" + linked.search() + ", writes=" + linked.writes());
choose(array, linked);
}
private static void choose(Cost array, Cost linked) {
int arrayTotal = array.search() + array.writes();
int linkedTotal = linked.search() + linked.writes();
System.out.println("scenario-winner=" + (arrayTotal < linkedTotal ? "array" : "linked"));
}
private record Cost(int search, int writes) {
Cost {
if (search < 0 || writes < 0) throw new IllegalArgumentException();
}
}
}작업 부하에 따른 이론표 해석
ArrayList get은 주소 계산 뒤 바로 원소를 읽지만 LinkedList get은 가까운 끝에서 Node를 따라갑니다.
반대로 첫 위치 삽입은 배열이 모든 원소를 미는 동안 연결 목록은 시작 참조 몇 개만 바꿉니다.
애플리케이션에서 각 연산이 몇 퍼센트인지 모르면 어느 장점이 중요한지 결정할 수 없습니다.
Study Log의 현실적인 부하는 끝 add 20%, 전체 순회 70%, 드문 삭제 10%처럼 기술할 수 있습니다.
이 경우 연결 목록의 첫 삽입 강점보다 연속 배열의 순회 지역성이 더 중요할 가능성이 큽니다.
목록 크기 분포도 평균과 상위 백분위를 함께 봅니다.
연산 수와 벽시계 시간 분리
결정적 비용 모델은 이동 칸, next 추적, 참조 대입을 셉니다.
구현 오류를 찾고 Big-O 전제를 확인하는 데 좋습니다.
실제 벽시계 벤치마크는 JIT 워밍업, GC, CPU 부하, 캐시 상태가 영향을 주므로 충분한 반복과 통계가 필요합니다.
System.nanoTime 한 번의 차이를 제품 결론으로 사용하면 잡음을 측정할 수 있습니다. JMH 같은 전용 도구를 사용하더라도 데이터 생성과 측정 코드를 분리하고, 두 구현이 같은 최종 결과를 만드는지 먼저 확인합니다.
연속 메모리와 노드 오버헤드
ArrayList의 참조 배열은 연속되어 순차 접근 때 캐시 라인을 효율적으로 사용합니다.
LinkedList는 각 Node 객체에 항목, prev, next가 있고 힙 여러 위치에 놓일 수 있습니다.
같은 원소 수라도 메모리 사용량과 포인터 추적 횟수가 다릅니다.
Java ArrayList의 이동은 최적화된 배열 복사를 활용합니다. LinkedList의 “대입 두 번”이 항상 더 빠르다는 결론은 위치 탐색, 할당, 캐시 미스가 빠진 설명입니다. 측정 결과가 없을 때는 단순성과 조회 성능이 좋은 ArrayList를 기본값으로 둡니다.
읽기·쓰기 비율 기록
Study Log CLI에서 일반 사용자는 전체 목록 조회와 끝 추가를 주로 수행합니다. 이 연산 분포라면 ArrayList가 단순하고 빠른 기본 선택입니다. 앞 삽입이 실제 병목이라는 관측이 생길 때만 다른 구조를 실험합니다.
public final class StudyLogCliCH148 {
public static void main(String[] args) {
StudyLog log = new StudyLog();
log.add("cost-model", 48);
log.add("cache-locality", 52);
log.print();
System.out.println("total=" + log.totalMinutes());
}
private static final class StudyLog {
private Entry[] entries = new Entry[2];
private int size;
void add(String topic, int minutes) {
if (topic == null || topic.isBlank()) throw new IllegalArgumentException("topic");
if (minutes <= 0) throw new IllegalArgumentException("minutes");
ensureCapacity(size + 1);
entries[size++] = new Entry(topic, minutes);
}
private void ensureCapacity(int required) {
if (required <= entries.length) return;
Entry[] grown = new Entry[Math.max(required, entries.length * 2)];
System.arraycopy(entries, 0, grown, 0, size);
entries = grown;
}
int totalMinutes() {
int total = 0;
for (int i = 0; i < size; i++) {
total += entries[i].minutes();
}
return total;
}
void print() {
for (int i = 0; i < size; i++) {
Entry entry = entries[i];
System.out.println(i + ":" + entry.topic() + "=" + entry.minutes());
}
}
}
private record Entry(String topic, int minutes) {}
}CLI 작업 부하는 두 번의 끝 추가, 한 번의 전체 출력, 한 번의 합계 순회입니다. 중간 삽입은 없습니다. 이 관찰만으로도 ArrayList를 기본 선택할 충분한 이유가 생기며, LinkedList를 택하려면 다른 실제 부하 증거가 필요합니다.
실제 작업 부하로 구현을 고르는 질문
| 질문 | 관찰할 값 | 선택 또는 조치 |
|---|---|---|
| 임의 조회 비율은 얼마인가 | get(index) 횟수 | 배열 가중 |
| 앞 변경 비율은 얼마인가 | index 0 변경 | 연결 가중 |
| 순차 순회가 중심인가 | 전체 스캔 횟수 | 캐시 효과 측정 |
| 위치 참조를 이미 갖는가 | Node 핸들 보유 | 연결 O(1) 인정 |
List 구현 선택은 단일 연산 표가 아니라 애플리케이션의 연산 혼합을 입력으로 합니다.
Java LinkedList는 양방향 링크와 first·last를 유지해 메모리 비용도 더 큽니다.
일반적인 기본값은 ArrayList이고 반대 증거가 있을 때 교체합니다.
연습 문제
크기 1000 목록에서 중간 조회 700회와 첫 삽입 3회를 수행한다고 가정합니다. 배열은 조회당 1, 첫 삽입당 1000의 비용을, 연결 목록은 중간 조회당 500, 첫 삽입당 1의 비용을 사용해 총점을 비교하세요.
정답과 해설
이 모델은 실제 나노초가 아니라 주어진 작업 수의 상대 비교입니다. 동일 공식과 입력을 코드로 고정해 계산 실수를 없앱니다.
public final class MixedListWorkloadSolution {
public static void main(String[] args) {
int reads = 700;
int frontInserts = 3;
int arrayCost = reads + frontInserts * 1_000;
int linkedCost = reads * 500 + frontInserts;
String choice = arrayCost < linkedCost ? "array" : "linked";
System.out.println("array=" + arrayCost + ", linked=" + linkedCost + ", choice=" + choice);
}
}배열 총점은 3700, 연결 총점은 350003이므로 이 가정에서는 배열이 선택됩니다. 작업 비율이나 단위 비용을 바꾸면 결론도 달라지므로 모델의 전제를 함께 기록해야 합니다.
측정 기반 선택 확인
두 구현에 같은 입력과 최종 결과를 사용했는지 먼저 확인합니다. 연산 수 모델과 실제 시간 측정을 섞어 단위를 잃지 않습니다. 워밍업과 반복 분포가 없는 단발 측정은 근거로 쓰지 않습니다. 기본 ArrayList를 바꿀 때는 관찰된 병목과 재현 가능한 부하가 있어야 합니다.