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

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

 

단순하게 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 일정 크기의 메모리를 더 덧붙이면 되겠지만 실제로는 다른 데이터가 저장되어 있을 확률이 높다.

 

따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다.

 

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

 

이 과정을 아래 코드와 같이 나타낼 수 있다.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    // int 자료형 3개로 이루어진 list라는 포인터를 선언하고 메모리 할당
    int *list = malloc(3 * sizeof(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)
    {
        free(list); // 할당된 메모리 해제
        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++)
    {
        printf("%i\n", list[i]);
    }

    // list의 메모리 해제
    free(list);

    return 0;
}

 

 

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

#include <stdio.h>
#include <stdlib.h>

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

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

    // realloc 함수를 사용하여 list의 크기를 4개의 int 자료형 크기로 재할당
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        free(list); // 할당된 메모리 해제
        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);

    return 0;
}

realloc 함수는 기존 메모리 블록을 확장하거나 축소할 때 유용하게 사용할 수 있다. 새로운 메모리 블록을 할당하고 기존 메모리 블록의 내용을 새로운 블록으로 복사한 후 기존 블록을 해제한다.

 

위 코드에서는 list 포인터를 realloc 함수로 재할당해 크기를 확장하고 이를 tmp에 저장한 뒤 다시 list에 대입해서 확장된 메모리를 사용한다.

 

 

References

모두를 위한 컴퓨터 과학 (CS50 2019)

모두를 위한 컴퓨터 과학 (CS50 2019)