자료구조(Data Structure)란, "자료를 효율적으로 관리하기 위한 구조 설계"를 의미합니다.

그리고 그런 자료구조를 공부한다는 것은, 결국 "데이터를 메모리에 어떻게 효율적으로 저장하고, 필요한 순간에 어떻게 빠르게 꺼내 쓸 것인가?"를 공부하는 것입니다.

그 시작은 항상 배열입니다. 배열이 자료구조의 첫 챕터를 장식하는 이유는, 스택(Stack), 큐(Queue), 힙(Heap), 해시 테이블(Hash Table) 등 수많은 고급 자료구조들이 결국 배열을 기반으로 구현되기 때문입니다.

이번 글에서는 컴퓨터 구조적 관점에서 배열에 대해 알아보고자 합니다.

배열의 핵심: '연속성(Contiguity)'

배열의 정의는 다음과 같습니다

"동일한 크기의 메모리 공간이 빈틈없이 연속적(Contiguously)으로 나열된 구조"

여기서 가장 중요한 키워드는 빈틈없이 연속적이라는 점입니다. 배열은 메모리 상에 배치될 때, 절대 흩어지거나 떨어져서 존재하지 않습니다.

첫 번째 데이터가 0x1000 번지에 저장되어 있다면, 두 번째 데이터는 반드시 0x1004 (4바이트 정수형 기준) 번지에 저장되어야 합니다. 중간에 빈 공간(Gap)은 절대 허용되지 않습니다.

이러한 물리적인 연속성은 배열이 가진 가장 강력한 무기입니다. 데이터가 나열된 순서(Index)만 알면, 복잡한 탐색 과정 없이 즉시 해당 데이터의 메모리 주소로 접근할 수 있기 때문입니다(Random Access).

Random Access

배열이 다른 자료구조(특히 연결 리스트)와 차별화되는 가장 큰 특징은 인덱스를 통한 접근 속도가 O(1)이라는 점입니다.

우리는 흔히 arr[0]에 접근하든, arr[10000]에 접근하든 속도 차이가 없다는 것을 알고 있습니다. 이것을 Random Access(임의 접근)라고 부릅니다.

배열은 연속적이고 데이터의 크기가 동일합니다. 따라서 시작 주소(Base Address)만 알면, 우리가 원하는 데이터의 주소를 단 한 번의 연산으로 계산해 낼 수 있습니다.

text

Target Address = Base Address + (Index × Data Size)

Base Address: 배열의 시작 주소 (예: 0x1000)
Index: 찾으려는 위치 (예: 3)
Data Size: 데이터 타입의 크기 (예: int는 4byte)

만약 3번째 인덱스(arr[3])의 데이터를 찾고 싶다면, CPU는 다음과 같이 계산합니다.

text

0x1000 + (3 × 4) = 0x1012

CPU는 이 덧셈과 곱셈 연산을 눈 깜짝할 사이에 처리하고, 계산된 0x1012 번지를 즉시 타격합니다.

데이터가 100만 개가 있더라도 마찬가지입니다. 처음부터 순서대로 훑어보는 과정(Iteration) 없이, 수식 한 번으로 정확한 위치를 찾아냅니다. 이것이 바로 배열이 조회(Read) 성능에서 압도적인 효율을 자랑하는 이유입니다.

연속성의 역설

하지만 모든 엔지니어링에는 트레이드오프(Trade-off)가 존재합니다. 배열에게 접근성을 선물했던 연속성은, 데이터를 수정해야 하는 순간 치명적인 족쇄로 돌변합니다.

1) 삽입과 삭제 문제

배열의 중간에 데이터를 삽입하거나 삭제하는 것은 배열에게 있어 가장 곤란한 작업입니다. 빈틈없는 연속성을 유지하기 위해, 건드리지 않은 나머지 데이터들까지 강제로 위치를 옮겨야 하기 때문입니다.

위 그림과 같이 int 배열의 중간에 새로운 데이터를 삽입(Insertion)한다고 가정해 봅시다.

데이터를 맨 뒤에 추가(Append)하는 상황이라면 빈 공간에 넣기만 하면 되니 아주 빠릅니다. 하지만 중간 삽입은 다릅니다. 누군가 새치기를 하려면 뒤에 있는 사람들이 모두 뒤로 물러나야 하듯, 삽입하려는 인덱스부터 마지막 데이터(Index 2 ~ 4)까지 전부 우측으로 한 칸씩 이동해야 공간이 확보됩니다.

삭제(Deletion)의 경우는 어떨까요? 상황은 반대지만 고통은 같습니다.

데이터가 삭제되면 메모리 중간에 구멍(Gap)이 생깁니다. 하지만 배열의 정의상 빈 공간은 절대 허용되지 않습니다. 따라서 구멍을 메꾸기 위해, 삭제된 위치 뒤에 있는 모든 데이터(Index 2 ~ 4)를 좌측으로 한 칸씩 당겨와야 합니다.

이처럼 배열의 중간에서 삽입/삭제가 발생하면, 필연적으로 내부 데이터들의 대규모 이동이 동반됩니다. 이를 공식적으로 Shift(이동) 연산이라고 부릅니다.

예시처럼 데이터가 적을 때는 문제가 없지만, 만약 데이터가 100만 개라면 어떨까요? 최악의 경우(맨 앞에 삽입/삭제 시) 100만 번의 이동 연산이 발생합니다.

이는 컴퓨터 자원을 낭비하는 주범이며, 시간 복잡도는 $$O(N)$$ 이라는 비효율을 낳습니다. 이것이 바로 삽입/삭제가 빈번한 로직에서 배열을 기피해야 하는 이유입니다.

2) 정적인 크기

연속성이 가져온 또 하나의 제약은 바로 크기가 고정된다는 점입니다.

배열을 선언한다는 것은 운영체제(OS)에게 "연속된 메모리 공간을 이만큼만 주세요"라고 예약하는 것과 같습니다. 예를 들어 int형 데이터 8개를 저장할 공간을 요청하면, OS는 딱 그만큼의 연속된 공간을 잘라서 내어줍니다.

그런데 사용하다 보니 데이터가 늘어나 9번째 데이터를 저장해야 할 순간이 왔습니다. 과연 기존 배열 뒤에 공간을 덧붙여서 확장할 수 있을까요?

위 그림처럼 8개의 int 공간이 꽉 차 있는 상황입니다. 상식적으로는 "뒤에 빈칸 하나만 더 붙이면 되지 않나?" 싶겠지만, 실제 메모리의 작동 방식은 그렇게 호락호락하지 않습니다.

메모리 할당은 철저하게 요구한 만큼만 이루어집니다. 그리고 OS는 메모리의 빈 공간을 효율적으로 쓰기 위해, 배열이 끝나는 지점 바로 다음 주소에 다른 변수나 프로세스의 데이터를 할당했을 확률이 매우 높습니다.

즉, 내 배열의 바로 뒷집에는 이미 누군가가 살고 있을 수도 있다는 뜻입니다.

만약 공간이 부족하다고 해서 강제로 데이터를 밀어 넣으면 어떻게 될까요? 내 배열의 범위를 넘어(Out of Bounds), 엄한 남의 메모리 영역을 침범하게 됩니다. 이 과정에서 다른 프로세스의 중요한 데이터를 덮어쓰거나 오염시킬 수 있으며, 이를 버퍼 오버플로우(Buffer Overflow)라고 부릅니다.

운영체제는 이러한 침범 행위를 심각한 위협으로 간주하고, 즉시 프로그램을 강제 종료(Segmentation Fault) 시켜버립니다.

그렇다면 공간이 부족할 땐 어떻게 해야 할까요? 방법은 하나뿐입니다. 이사(Migration)를 가야 합니다.

더 큰 크기(예: 16개)의 새로운 배열을 힙(Heap) 메모리의 다른 곳에 할당받습니다.
기존 배열에 있던 데이터 8개를 새로운 배열로 하나씩 복사(Copy)합니다.
기존 배열은 메모리에서 해제(Free)합니다.

이 과정을 리사이징(Resizing)이라고 합니다. 하지만 이 또한 데이터를 전부 복사해야 하므로 $$O(N)$$ 의 비용이 발생하는 매우 무거운 작업입니다.

따라서 배열은 데이터의 최대 개수를 미리 알 수 없거나, 크기가 빈번하게 변하는 상황에서는 유연하지 못한 자료구조입니다.

지금까지 컴퓨터 구조적 관점에서 배열의 본질인 연속성(Contiguity)과 그에 따른 장단점을 살펴보았습니다.

정리하자면, 배열은 읽기(Read)에 최적화되어 있고, 쓰기(Write)에는 취약한 자료구조입니다.

장점 (Pros):
- 압도적인 조회 속도: 인덱스만 알면 $$O(1)$$ 의 속도로 즉시 접근 가능합니다.
- 캐시 지역성(Cache Locality): 데이터가 인접해 있어 CPU 캐시 적중률(Hit Rate)이 매우 높습니다.
단점 (Cons):
- 비효율적인 쓰기: 중간 삽입/삭제 시 데이터 이동(Shift) 비용이 O(N) 발생합니다.
- 고정된 크기: 초기 선언 크기를 넘어서면, 더 큰 공간으로 이사(Resizing)하는 과정에서 O(N) 비용이 듭니다.

따라서 여러분의 데이터가 최대 크기를 예측할 수 있고, 빈번한 조회(Lookup)가 필요하며, 데이터의 변동이 적다면 배열은 최고의 선택이 될 것입니다.

연속성을 포기한다면?

하지만 개발을 하다보면 데이터가 얼마나 들어올지 예측할 수 없거나, 중간에 쓰기(write)가 계속해서 발생하는 상황은 흔합니다. 자료구조란 자료를 효율적으로 관리하기 위한 구조 설계입니다. 이러한 상황에서도 배열을 사용할 수는 없습니다.

그렇다면 연속성을 포기하면 됩니다.

연속성 대신 유연성을 취하면 이러한 상황에서 더욱 유연하게 대처가 가능하게 됩니다. 바로 다음글에서 연결 리스트(Linked List) 에 대해서 살펴봅시다.