배열은 연속된 메모리에 놓여 임의 접근(인덱스로 바로 접근)이 O(1) 이고, 연결 리스트는 흩어져 있어 순서대로 따라가야 합니다. 이 차이에서 나머지 성능 특성이 갈립니다.
배열 vs 연결리스트
데이터를 순서대로 저장하는 두 가지 기본 자료구조. 메모리 구조와 성능 특성이 정반대.
메모리 구조
[배열] 연속된 메모리
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
0x100 104 108 10C 110
[연결리스트] 흩어진 메모리
┌───┬──┐ ┌───┬──┐ ┌───┬──┐
│ A │ →├─→│ B │ →├─→│ C │ ∅│
└───┴──┘ └───┴──┘ └───┴──┘
0x200 0x500 0x300
시간 복잡도 비교
연산
배열
연결리스트
인덱스 접근
O(1)
O(N)
앞에 삽입
O(N)
O(1)
뒤에 추가
O(1)*
O(1)
중간 삽입
O(N)
O(1)+탐색
검색
O(N)
O(N)
메모리
연속 필요
분산 가능
*동적 배열 amortized
언제 무엇을 쓸까?
상황
선택
이유
인덱스로 자주 접근
배열
O(1) 접근
삽입/삭제 빈번
연결리스트
O(1) 삽입
크기 고정
배열
메모리 효율
크기 가변적
연결리스트
동적 할당
캐시 성능 중요
배열
캐시 지역성
캐시 지역성 (실무에서 중요!)
[배열] CPU 캐시에 한번에 로드
→ 연속 메모리 → 캐시 히트율 높음
→ 실제 성능 우수
[연결리스트] 메모리 곳곳에 흩어짐
→ 캐시 미스 빈번 → 실제 성능 저하
→ 실무에서는 배열(ArrayList)이 대부분 유리
면접에서 이렇게 나옵니다
Q.배열과 연결리스트의 차이를 설명해주세요.
메모리에 놓이는 방식이 다르고, 거기서 모든 차이가 나옵니다.
항목
배열
연결 리스트
배치
연속된 한 덩어리
노드가 흩어져 포인터로 이어진다
위치 찾기
주소 계산으로 즉시
처음부터 따라가며
크기
미리 정한다. 넘으면 새로 만들어 복사
필요할 때 노드를 더한다
추가 메모리
없음
노드마다 포인터
연속이라는 성질이 O(1) 접근을 주고, 그 대가로 중간 삽입에 시프트를 요구합니다. 연결이라는 성질은 그 반대입니다.
흔한 실수: 표만 외워 "삽입이 많으면 연결 리스트"라고 답하는 것. 실무에서는 캐시 효율 때문에 수천 개 이하에서는 배열이 이기는 경우가 많습니다.
Q.배열과 연결리스트의 시간복잡도 차이를 설명해주세요
접근과 수정이 정반대입니다.
연산
배열
연결 리스트
i번째 읽기
O(1)
O(n)
맨 앞 삽입
O(n)
O(1)
중간 삽입
O(n)
위치를 알면 O(1), 찾아야 하면 O(n)
맨 뒤 추가
분할상환 O(1)
꼬리를 들고 있으면 O(1)
배열은 시작 주소에 인덱스를 곱해 더하면 위치가 나오므로 한 번에 갑니다. 대신 중간에 넣으면 뒤를 모두 밀어야 합니다. 연결 리스트는 반대로 포인터만 바꾸면 되지만, 그 자리에 가려면 처음부터 세어 가야 합니다.
흔한 실수: 연결 리스트의 중간 삽입을 그냥 O(1)이라고 답하는 것. 노드를 이미 들고 있을 때만 O(1)이고, 인덱스로 찾아야 하면 탐색 O(n)이 먼저 붙습니다.
Q.배열의 삽입이 O(N)인 이유는?
연속 배치를 유지해야 하므로 빈 자리를 만들려면 뒤쪽을 모두 밀어야 합니다.
[10, 20, 30, 40] 의 앞에 5 를 넣는다
40, 30, 20, 10 을 한 칸씩 뒤로 옮긴다 <- n번
0번 자리에 5 를 넣는다
옮기는 개수가 삽입 위치에 따라 달라집니다. 맨 뒤는 0번, 맨 앞은 n번이고 평균은 n의 절반입니다. 상수를 버리면 O(n)입니다.
흔한 실수: 맨 뒤 추가도 O(n)이라고 답하는 것. 여유 공간이 있으면 O(1)이고, 용량이 찼을 때만 새 배열로 복사해 O(n)입니다. 확장이 배수로 일어나므로 여러 번 추가하면 분할상환 O(1)이 됩니다.
Q.캐시 지역성이란 무엇이고 왜 배열이 유리한가요?
방금 접근한 데이터와 그 주변을 곧 다시 쓸 가능성이 높다는 성질입니다. CPU는 이 성질을 믿고 64바이트 캐시 라인 단위로 미리 가져옵니다.
종류
뜻
시간 지역성
방금 쓴 데이터를 곧 다시 쓴다
공간 지역성
방금 쓴 데이터의 옆을 곧 쓴다
배열은 공간 지역성이 좋습니다. int 배열이면 라인 하나에 16개가 함께 실려 와서, 순회 중 캐시 미스가 16번에 한 번만 납니다. 연결 리스트는 노드가 흩어져 있어 접근마다 새 라인을 가져올 수 있습니다.
L1 캐시는 1ns 안팎이고 메모리는 100ns 안팎이라 이 차이가 수십 배로 벌어집니다.
흔한 실수: 지역성을 메모리 사용량 문제로 설명하는 것. 얼마나 쓰느냐가 아니라 다음에 쓸 것이 이미 캐시에 있느냐의 문제입니다.
Q.연결리스트가 배열보다 적합한 상황은?
삭제할 노드를 이미 가리키고 있고, 그 삭제가 잦은 경우입니다.
상황
이유
LRU 캐시의 순서 관리
해시 맵이 노드를 바로 주므로 떼어내기가 O(1)
OS의 대기 큐, 실행 큐
특정 프로세스를 중간에서 빼는 일이 잦다
해시 테이블의 충돌 체인
같은 버킷의 항목을 이어 붙인다
메모리 할당기의 빈 블록 목록
블록 안에 다음 블록 주소를 적어 추가 메모리가 없다
공통점은 인덱스로 찾지 않는다는 것입니다. 인덱스로 찾아야 하면 탐색 O(n)이 붙어 이득이 사라집니다.
흔한 실수: "삽입과 삭제가 많으면 연결 리스트"로 뭉뚱그리는 것. 위치를 어떻게 얻는지가 실제 기준입니다.