자료구조 면접 퀴즈

연속된 메모리에 같은 크기로 놓기 때문에 인덱스로 위치를 계산할 수 있고, 그래서 임의 접근이 O(1) 입니다.

배열 (Array)

메모리 구조

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

시간 복잡도

실무 포인트

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

왜 붙어 있는 것이 빠른가

칸의 위치를 계산으로 얻는 것은 절반입니다. 나머지 절반은 한 번 읽을 때 주변까지 같이 가져온다는 점입니다.

같은 원소 수인데 몇 배가 갈립니다. 그래서 2차원 배열은 저장된 방향과 같은 방향으로 훑습니다. 이것이 알고리즘 표기에는 안 나타나지만 실제 시간에는 나타납니다.

늘어날 때 무슨 일이 일어나나

크기가 정해진 배열이라 넘치면 새로 만들어 옮깁니다.

넘칠 때마다 크기를 두 배로 잡는다
그래서 옮기는 비용을 나눠 보면 넣는 것이 일정한 시간에 가깝다
다만 그 순간 하나는 원소 수만큼 걸린다

셋째가 지연 그래프의 튀는 점입니다. 넣을 개수를 미리 알면 처음부터 그만큼 잡아 옮기기를 없앱니다.

면접 키워드

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

각 노드가 다음 노드를 포인터로 가리킵니다. 위치를 계산할 수 없어 순차 접근만 되고, 대신 삽입과 삭제에서 원소를 밀지 않습니다.

연결 리스트 (Linked List)

구조

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

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

시간 복잡도

배열 vs 연결 리스트

중간 삽입이 빠르다는 말의 조건

노드를 알고 있으면 잇는 것은 즉시 끝납니다. 다만 그 노드를 찾는 것은 앞에서부터 세어야 합니다.

그래서 이 자료구조는 순회하면서 넣고 빼는 경로에서 값이 있습니다. 위치로 접근하는 경로에서는 배열이 낫습니다. 표기상 같은 O(1) 이라도 조건이 다릅니다.

흩어져 있는 대가

노드가 메모리 곳곳에 있어 순서대로 훑어도 붙어 있는 배열보다 느립니다.

노드마다 다음 위치를 따라가야 한다
가져온 덩어리 안에 다음 노드가 있을 보장이 없다
노드마다 다음을 가리키는 공간이 따로 든다

셋째도 작지 않습니다. 작은 값을 많이 담으면 값보다 연결 정보가 차지하는 몫이 커집니다. 그래서 실무 목록은 대부분 배열 기반입니다.

실무 포인트

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

배열은 연속된 메모리에 놓여 임의 접근(인덱스로 바로 접근)이 O(1) 이고, 연결 리스트는 흩어져 있어 순서대로 따라가야 합니다. 이 차이에서 나머지 성능 특성이 갈립니다.

배열 vs 연결리스트

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

메모리 구조

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

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

시간 복잡도 비교

*동적 배열 amortized

언제 무엇을 쓸까?

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

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

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

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