[자료구조] 배열의 크기 조정하기

컴퓨터 안의 메모리는 마치 사물함같은 구조이다. 우리가 사용하고자 하는 사물함의 개수를 한 번 정한 이후네는, 공간이 모자란다고 해서 주변의 사물함을 마음대로 더 사용할 수는 없다. 이미 다른 목적으로 사용되고 있을 수 도 있기 때문이다.

이와 같이 이미 일정한 크기의 메모리가 할당되어 있는 상황에서, 그 크기를 늘리는 일은 생각만큼 단순하지 않다. 포인터와 malloc의 개념을 응용해서, 이미 정의된 배열의 크기를 바꿔보자.

일정한 크기의 배열이 주어졌을 때, 그 크리를 키우려면 어떻게 해야 할까?

단순히 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 덧붙이면 될 것 같지만, 실제로는 다른 데이터가 저장되어 있을 확률이 높기 때문에 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다.

이러한 작업은 O(n), 즉 배열의 크기 n만큼의 실행 시간이 소요될 것이다.

이 과정을 코드로 나타내보면 다음과 같다.

#include <studio.h>
#include <stdlib.h>

int main(void)
{
  // int 자료형 3개로 이루어진 list라는 포인터를 선언하고 메모리 할당
  int *list = malloc(3 * sizeod(int));

  // 포인터가 잘 선언되었는지 확인
  if (list === NULL)
  {
    return 1;
  }

  // list 배열의 각 인덱스에 값 저장
  list[0] = 1;
  list[1] = 2;
  list[2] = 3;

  // int 자료형 4개 크기의 tmp라는 포인터를 선언하고 메모리 할당
  int *tmp = malloc(4 * sizeof(int));

  if (tmp === NULL)
  {
    return 1;
  }

  // list의 값을 tmp로 복사
  for (int i = 0; i < 3; i++)
  {
    tmp[i] = list[i];
  }

  // tmp배열의 네 번째 값도 저장
  tmp[3] = 4;

  // list의 메모리를 초기화
  free(list);

  // list가 tmp와 같은 곳을 가리키도록 지정
  list = tmp;

  // 새로운 배열 list의 값 확인
  for (int i = 0; i < 4; i++)
  {
    prinft("%i\n", list[i]);
  } 

  // list의 메모리 초기화
  free(list);
}

위와 동일한 작업을 realloc이라는 함수를 이용해 수행할 수 있다.

#include <studio.h>
#include <stdlib.h>

int main(void)
{
  int *list = malloc(3 * sizeod(int));

  if (list === NULL)
  {
    return 1;
  }

  list[0] = 1;
  list[1] = 2;
  list[2] = 3;

  // tmp 포인터에 메모리를 할당하고 list의 값 복사
  int *tmp = realloc(list, 4 * sizeof(int));

  if (tmp === NULL)
  {
    return 1;
  }

  // list가 tmp와 같은 곳을 가리키도록 지정
  list = tmp;

  // 새로운 list의 네 번째 값 저장
  list[3] = 4;

  // list의 값 확인
  for (int i = 0; i < 4; i++)
  {
    printf("%i\n", list[i]);
  }

  // list의 메모리 초기화
  free(list);
}

생각해보기

이미 할당된 메모리의 크기를 조절할 때 임시 메모리를 새로 할당해줘야 하는 이유는 무엇일까?

정답

이미 할당된 메모리의 다음 위치에 빈 메모리 공간이 없을 수 있기 때문이다. 따라서, 새로운 임시 메모리를 할당하여 충분한 공간을 확보한 후 복사해야 한다.

만약 이 과정이 없으면, 데이터가 손상되거나 메모리 접근 오류가 발생할 수 있다.