개발을 하다 보면 당연하게 여기는 것들이 있습니다. 자바 개발자로써 저는 거의 매일 사용하는 List.add()가 그렇습니다. 배열의 크기를 신경 쓰지 않아도 데이터는 계속 들어가고, 알아서 늘어납니다.
하지만 컴퓨터의 세계에 '무한한 배열' 같은 것은 없습니다.
무한한 배열은 없다 - ArrayList에서 저는 Java의 ArrayList가 내부적으로 어떻게 동작하는지, 그 확장의 원리를 이론적으로 살펴보았습니다. Java는 개발자가 비즈니스 로직에 집중할 수 있도록 복잡한 메모리 관리를 간단히 추상화해 줍니다. 덕분에 우리는 Capacity가 찼을 때의 이사(Migration) 비용이나, 메모리 해제 타이밍을 크게 고민하지 않아도 되었죠.
"그렇다면, 그 보호막을 걷어내면 어떤 일이 벌어질까요?"
오늘은 그 편리함 뒤에 숨겨진 진짜 '비용'을 계산해보려 합니다. 가비지 컬렉터(GC)도, 자동화된 확장 메서드도 없는 C언어의 환경에서 ArrayList를 바닥부터 다시 만들어보겠습니다.
직접 메모리를 할당(malloc)하고, 공간이 부족하면 땅을 넓히고(realloc), 데이터를 옮기는 과정을 통해, 우리가 당연하게 누렸던 편리함이 사실은 얼마나 정교한 엔지니어링의 산물인지 확인해 보려 합니다.
동적 배열 구현하기
Java에서는 Class 하나에 데이터(필드)와 행동(메서드)을 모두 담지만, C언어는 다릅니다. 데이터의 형태를 정의하는 구조체(Struct)와, 그 데이터를 조작하는 함수(Function)를 명확히 분리해서 생각해야 합니다.
우리가 구현할 ArrayList는 어떤 모습이어야 할까요? 가장 먼저 데이터의 그릇이 될 구조체(ADT)부터 정의해 보겠습니다.
1. 상태 정의: 무엇을 관리해야 하는가?
일반적인 배열 int arr[10];을 선언하면 크기가 고정됩니다. 하지만 우리는 크기가 변하는 배열을 만들어야 하죠. 이를 위해 힙(Heap) 메모리를 사용해야 하고, 이 동적인 메모리를 관리하기 위해선 세 가지 핵심 정보가 항상 따라다녀야 합니다.
- 데이터의 위치 (
Pointer): 실제 데이터가 저장된 힙 메모리의 주소입니다. - 현재 데이터의 개수 (
Size): 사용자가 실제로 채워 넣은 데이터의 양입니다. - 현재 허용 용량 (
Capacity): 우리가 미리 확보해 둔 메모리의 총 크기입니다.
이 개념을 코드로 옮기면 다음과 같습니다.
typedef struct IntArrayList {
int *data;
int currentSize;
int currentCapacity;
} IntArrayList;구조체를 정의했다고 끝이 아닙니다. 이것은 설계도일 뿐, 실제 메모리 공간에는 존재하지 않기 때문입니다. 이제 이 설계도를 바탕으로 힙(Heap) 메모리에 공간을 할당하는 생성자 함수를 만들어야 합니다.
2. 자료구조 생성
C언어에서 자료구조 생성이라고 한다면 구조체를 메모리에 할당하는 것이죠. 그리고 이번에도 어김없이 메모리 할당을 해야합니다.
그러나 주의할 점은 항상 구조체와 데이터 배열을 따로 할당해야 합니다.
IntArrayList *createIntArrayList(int initialCapacity) {
// 1. 리스트 관리 구조체 할당
IntArrayList *pList = (IntArrayList *) calloc(1, sizeof(IntArrayList));
if (pList == NULL) return NULL; // 메모리 부족 방어 로직
// 2. 실제 데이터가 저장될 내부 배열 할당
pList->data = (int *) calloc(initialCapacity, sizeof(int));
// 만약 배열 할당에 실패했다면?
if (pList->data == NULL) {
free(pList); // 앞서 만든 구조체도 책임지고 해제해야 합니다. (롤백)
return NULL;
}
pList->currentCapacity = initialCapacity;
// calloc()으로 구조체를 메모리에 할당 시켰다면 0으로 초기화 되므로 해당 코드는 불필요합니다.
// 하지만 코드 가독성을 위해 명시적으로 적습니다.
pList->currentSize = 0;
return pList;
}C언어는 메모리를 다루는 만큼, 메모리 누수가 발생하지 않도록 방어적인 코드 작성을 하는 것에 주의하세요.
3. 추가와 확장
이제 ArrayList의 핵심이라고 할 수 있는 데이터 추가 기능을 구현해 보겠습니다.
사용자 입장에서는 단순한 데이터 추가일 뿐이겠지만, 내부에서는 배열에 데이터를 넣을 수 있는 공간이 있는지 검증이 필요합니다.
공간이 남아있다면 단순히 값을 대입하면 되겠지만 그렇지 않다면 반드시 확장을 해야만 합니다.
이사(Migration)의 비용
배열이 가득 찼을 때(Size >= Capacity), 우리는 더 큰 메모리 공간을 찾아야 합니다. 이를 Grow()라고 합니다.
C언어에서는 realloc()함수를 통해 이를 수행합니다. 하지만 realloc()은 단순히 기존 공간 뒤에 메모리를 추가해주는 기능이 아닙니다. 뒤쪽 메모리에 여유가 없다면, 메모리의 다른 곳에 더 넓은 땅을 찾고, 기존 데이터를 전부 복사해서 옮긴 뒤, 예전 땅을 폐기하는 대공사를 수행합니다.
오늘날 컴퓨터의 성능을 생각한다면 이 비용은 사실 값비싼 것은 아닙니다만, 그래도 이 작업이 빈번히 일어난다면 매우 큰 비효율일 수 밖에 없습니다.
그래서 여기서는 두배 확장 전략을 사용합니다. 한 번 이사할 때 넉넉잡아 2배로 넓혀두면 당분간은 이사 걱정없이 데이터를 채울 수 있기 때문입니다. 이를 분할 상환 분석(Amortized Analysis)라고 합니다.
(자바에서의 ArrayList 증가 코드는 1.5배입니다. 이 경우 더 정교한 증가가 가능하지만 모든 선택은 결국 개발자에게 달려있습니다.)
// 내부적으로 사용될 확장 함수
int grow(IntArrayList *plist) {
int current = plist->currentCapacity;
// 0이면 10으로 초기화, 아니면 2배 확장
int newCapacity = (current == 0) ? 10 : current * 2;
// realloc: 기존 데이터를 유지하며 메모리 크기를 조절합니다.
// [주의] 실패 시 NULL을 반환하므로 반드시 임시 포인터로 받아야 합니다.
// 만약 바로 plist->data에 받으면, 실패 시 원본 데이터의 주소를 잃어버리게 됩니다.
int *tempData = (int *) realloc(plist->data, newCapacity * sizeof(int));
if (tempData == NULL) {
return 0; // 확장 실패
}
plist->data = tempData; // 주소 갱신 (이사가 성공했을 때만)
plist->currentCapacity = newCapacity; // 용량 갱신
return 1; // 성공
}
int add(IntArrayList *plist, int item) {
if (plist == NULL) return 0;
// 1. 공간이 부족한지 확인 (Size가 Capacity를 넘어설 때)
if (plist->currentSize >= plist->currentCapacity) {
// 확장을 시도하고, 실패하면 데이터 추가도 포기합니다.
if (grow(plist) == 0) {
return 0;
}
}
// 2. 데이터 추가 (인덱스는 0부터 시작하므로 currentSize가 곧 인덱스)
plist->data[plist->currentSize] = item;
plist->currentSize++;
return 1; // 성공
}여기서 눈여겨볼 점은 realloc의 반환값을 tempData라는 임시 변수에 받는 것입니다. 메모리 확장에 실패했을 때 원본 데이터를 보호하기 위한 최소한의 안전장치입니다.
4. 뒷정리의 책임: 자바에는 있고 C에는 없는 것
여기까지 우리는 데이터를 담고, 공간을 늘리는 법을 배웠습니다. 하지만 C언어의 야생에서는 한 가지 절차가 더 남아있습니다. 바로 뒷정리입니다.
Java에서는 우리가 만든 ArrayList를 다 쓰고 나서 잊어버려도 됩니다. 똑똑한 가비지 컬렉터(GC)가 알아서 메모리를 수거해가기 때문이죠.
하지만 C언어는 그렇지 않습니다. 앞서 말했듯, C언어에서 메모리를 다루는 일은 매우 신중해야 합니다. 따라서 자료구조를 삭제(destroy)할 때도 정확한 구현이 필요합니다.
void destroyIntArrayList(IntArrayList *plist) {
if (plist == NULL) return;
// 1. 내부 데이터 배열부터 해제
if (plist->data != NULL) {
free(plist->data);
}
// 2. 구조체 해제
free(plist);
}순서가 중요합니다. 구조체(plist)를 먼저 해제해버리면, 그 안에 있는 data 포인터에 접근할 수 없게 되어 내부 배열은 영원히 미아가 됩니다. 따라서 데이터부터 삭제해야하는 서순에 주의하세요.
마치며: 마법은 없다.
백문이 불여일견, 모든건 해보기전까지는 모릅니다.
Java의 ArrayList는 개발자의 생산성을 위해 메모리 관리라는 복잡한 문제를 '추상화(Abstraction)'로 감춰두었습니다. 하지만 감춰졌다고 해서 사라진 것은 아닙니다. 내부에서는 여전히 malloc과 realloc, 그리고 copy가 발생하고 있으며, 이것은 모두 컴퓨팅 자원을 소모하는 '비용'입니다.
이 구조를 이해하고 나면 코드를 바라보는 관점이 달라집니다.
예를 들어, 데이터의 크기를 대략적으로라도 알 수 있다면 new ArrayList<>(100)처럼 초기 용량을 설정하는 것이 왜 중요한지 이해하게 됩니다. 불필요한 realloc과 데이터 이동(Shifting) 비용을 줄일 수 있기 때문입니다.
고수준 언어가 메모리를 관리해 준다는 것은, 개발자가 메모리에 대해 몰라도 된다는 뜻이 아닙니다. 도구가 감춰둔 비용을 정확히 인지하고 사용할 때, 비로소 엔지니어는 도구에 지배당하지 않고 도구를 온전히 통제할 수 있게 됩니다.
