자료구조 면접 퀴즈

배열 (Array)

메모리 구조

주소가 4씩 일정하게 늘어납니다. 연속된 메모리 공간에 놓이기 때문입니다.

시간 복잡도

실무 포인트

• 캐시 지역성: 연속 메모리라 CPU 캐시 히트율 높음
• Java ArrayList: 내부적으로 배열. 조회 많으면 유리
• 동적 배열: 용량 초과 시 2배로 확장 후 복사 (amortized O(1))

면접 키워드

"배열은 왜 인덱스 접근이 O(1)인가?" → 연속 메모리 + 주소 계산

연결 리스트 (Linked List)

구조

단일 연결 리스트:
[10|→] → [20|→] → [30|→] → null
 head

이중 연결 리스트:
null ← [←|10|→] ⇄ [←|20|→] ⇄ [←|30|→] → null
         head                        tail

시간 복잡도

배열 vs 연결 리스트

실무 포인트

• Java LinkedList: Deque 인터페이스 구현 (큐/스택 모두 가능)
• LRU 캐시: 이중 연결 리스트 + 해시맵 조합
• 실무에서는 캐시 지역성 때문에 ArrayList가 대부분 빠름

배열 vs 연결리스트

데이터를 순서대로 저장하는 두 가지 기본 자료구조. 메모리 구조와 성능 특성이 정반대.

메모리 구조

[배열] 연속된 메모리
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
0x100 104 108 10C 110

[연결리스트] 흩어진 메모리
┌───┬──┐  ┌───┬──┐  ┌───┬──┐
│ A │ →├─→│ B │ →├─→│ C │ ∅│
└───┴──┘  └───┴──┘  └───┴──┘
0x200     0x500     0x300

시간 복잡도 비교

*동적 배열 amortized

언제 무엇을 쓸까?

캐시 지역성 (실무에서 중요!)

[배열] CPU 캐시에 한번에 로드
→ 연속 메모리 → 캐시 히트율 높음
→ 실제 성능 우수

[연결리스트] 메모리 곳곳에 흩어짐
→ 캐시 미스 빈번 → 실제 성능 저하

→ 실무에서는 배열(ArrayList)이 대부분 유리