둘 다 시퀀스를 저장하지만 정반대의 비용 프로파일을 가집니다. array는 O(1) 인덱싱이 가능한 연속 메모리이고, linked list는 포인터로 이어진 흩어진 노드들로, 양 끝에서의 삽입/제거는 O(1)이지만 인덱싱은 불가능합니다.
| 연산 | Array (dynamic) | Linked list |
|---|
| index로 접근 | O(1) | O(n) |
| 검색 | O(n) | O(n) |
| head에서 insert/delete | O(n) | O(1) |
| tail에서 insert/delete | O(1) amortized | tail 포인터 시 O(1) |
| 중간에서 insert/delete | O(n) | O(n) 탐색 + O(1) splice |
| 메모리 오버헤드 | 낮음 | 높음(노드마다 포인터) |
| 캐시 지역성 | 우수 | 나쁨 |
Array: [10][20][30][40] <- 하나의 연속된 블록
Linked list: [10|*]->[20|*]->[30|null] <- 흩어진 노드들
실무에서는 대부분의 경우 array가 승리하는데, 일반적인 크기에서는 캐시 지역성이 Big-O 차이를 압도하기 때문입니다.
둘 다 알면 면접에서 맹목적으로 기본값을 고르는 대신 선택을 정당화할 수 있고, "O(1) 삽입"이 왜 연속된 array를 거의 이기지 못하는지 설명할 수 있습니다.