배열의 가장 큰 특징은 같은 타입의 데이터를 연속된 메모리 공간에 저장한다는 점이다. 예를 들어 int가 4바이트이고 배열의 시작 주소가 1000이라면, arr[3]의 주소는 1000 + 3 * 4로 바로 계산할 수 있다. 배열의 인덱스 접근이 O(1)인 이유가 여기에 있다.
주소: 1000 1004 1008 1012 1016
값: 10 20 30 40 50
인덱스: [0] [1] [2] [3] [4]연결리스트처럼 앞에서부터 하나씩 따라갈 필요가 없다. 시작 주소, 인덱스, 요소 크기만 알면 원하는 위치를 한 번의 계산으로 찾는다. 그래서 배열은 랜덤 접근이 많을 때 강하다. DP 테이블, 행렬, 정렬된 데이터에서의 이진 탐색처럼 “몇 번째 원소”를 자주 찾는 상황에서 배열이 자연스럽다.
2차원 배열도 결국 연속 메모리다
2차원 배열도 겉으로는 행과 열이 있는 표처럼 보이지만, 실제 메모리에는 한 줄로 펼쳐져 저장된다. C나 Java의 일반적인 배열 설명에서는 행 우선(row-major) 배치를 기준으로 이해하면 된다.
matrix[2][3] = {{1, 2, 3}, {4, 5, 6}}
메모리: 1 2 3 4 5 6
인덱스: [0,0] [0,1] [0,2] [1,0] [1,1] [1,2]그래서 2차원 배열을 순회할 때는 보통 바깥 반복문이 행, 안쪽 반복문이 열이 되도록 돈다. 메모리에 놓인 순서대로 접근하면 CPU 캐시를 더 잘 활용할 수 있기 때문이다.
캐시 친화성이 실제 성능을 만든다
배열은 이론적인 시간복잡도뿐 아니라 실제 성능에서도 유리한 경우가 많다. CPU가 메모리에서 값을 하나 읽을 때 그 값 하나만 가져오는 것이 아니라 주변 값까지 캐시 라인에 함께 가져온다. 배열은 값들이 붙어 있으므로 arr[0]을 읽은 뒤 arr[1], arr[2]를 읽을 때 캐시에 이미 올라와 있을 가능성이 높다.
반대로 연결리스트의 노드는 메모리 곳곳에 흩어져 있을 수 있다. 다음 노드로 이동할 때마다 새로운 메모리 위치를 따라가야 하므로 캐시 미스가 잦아진다. 시간복잡도 표만 보면 연결리스트가 좋아 보이는 상황에서도 실제로는 배열이나 ArrayList가 더 빠른 일이 많은 이유다.
면접에서 말할 포인트
배열은 연속 메모리와 동일한 요소 크기 덕분에 주소 계산이 가능하고, 그래서 인덱스 접근이 O(1)이다. 또한 메모리 지역성이 좋아 순차 순회에서 캐시 효율이 좋다. 단점은 크기가 고정된 배열의 경우 확장이 어렵고, 앞이나 중간 삽입/삭제 시 요소를 이동해야 해서 O(n)이 된다는 점이다.