2과목 · 37 해설 6

③

정답

연결 리스트 임의 접근은 O(1)이 아니라 O(n)이다

핵심 키워드

"O(n) 순차 접근"

선지별 분석

① ✅	배열은 시작 주소 + 인덱스×크기로 바로 계산 → O(1) 임의 접근. 정답.
② ✅	포인터로 연결되어 크기를 미리 고정하지 않아도 됨 → 동적 메모리 할당. 정답.
③ ❌	연결 리스트는 헤드부터 포인터를 따라가야 함 → O(n) 순차 접근. O(1)은 배열의 특권.
④ ✅	이중 연결 리스트는 prev·next 두 포인터 → 양방향(앞·뒤) 이동. 정답.

합격 공식 — 배열 vs 연결 리스트

배열 = 접근 강자 O(1) · 연결 리스트 = 삽입·삭제 강자 O(1). 거꾸로 표현하면 그게 오답.

단골 함정 "연결 리스트 O(1) 임의 접근" → O(n). O(1)은 배열.