연속된 메모리: arr[i] 가 왜 즉시인가

"배열의 마법은 많은 걸 담는 게 아니야. 한 줄로 담아서, 찾는 게 아니라 산술로 그중 아무거나 찾을 수 있다는 거야."

똑같은 상자 한 줄

메모리를 번호 매겨진 집들의 끝없는 거리로 그려봐. 배열은 그 거리 위, 어떤 주소에서 시작해 똑같고 같은 크기인 상자들을 등을 맞대 놓은 블록이야. 0번 상자는 시작점. 1번 상자는 바로 그 뒤. i번째 상자는 정확히 시작점에서 i 상자-너비 뒤야.

그 배치가 트릭 전부야. 원소 i 를 찾으려고 컴퓨터는 배열을 뒤지지 않아 — 주소를 직접 계산해: address = base + i × box_size. 곱 한 번, 합 한 번, 곧장 점프. 그래서 arr[5] 랑 arr[5_000_000] 이 정확히 같은 시간이 걸려: 둘 다 주소 계산 한 번이야. 이걸 임의 접근 (random access) 이라 하고, 배열을 정의하는 초능력이야.

배열의 모든 게 여기서 따라 나와

"한 줄의 똑같은 상자" 가 보이면, 배열의 모든 속성이 당연해져:

• 인덱싱은 O(1) — 그냥 주소 산술.
• 상자는 같은 크기여야 함 — 아니면 주소 공식이 깨져. 그래서 배열은 한 타입을 담고, 언어들이 가변 크기인 것 (문자열 같은) 을 그것들을 가리키는 포인터 배열로 저장하는 거야.
• 중간 삽입은 O(n) — 빈틈이 없어서 하나 열려면 뒤 상자를 다 밀어야 해.
• 크기가 고정 됨 (저수준에서) — 키우려면 더 큰 블록 할당하고 복사 (분할 상환 분석에서 본 그 두 배 하기).

조용한 보너스: 캐시 지역성

"연속" 에 숨은 두 번째 선물이 있어. CPU 가 배열 원소 하나를 읽으면, 이웃 덩어리 통째로를 초고속 캐시에 끌어와, 다음에 이웃을 원할 거라 베팅하면서 — 배열이면 보통 진짜 그래. 그래서 배열 훑기는 이론상 O(n) 일 뿐 아니라 실전에서 빠른 O(n) 이야, 하드웨어가 묻기도 전에 다음 원소를 먹여주거든. 이거 붙잡아둬 — 연결 리스트를 만나면, 흩어진 메모리가 이 보너스를 내버려서, 빅오가 암시하는 것보다 더 중요해.

피파의 고백