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

❄️ David Malan 교수의 모두를 위한 컴퓨터 과학(CS50 2019)을 바탕으로 정리한 내용입니다.

일정한 크기의 배열이 주어졌을 때, 그 크기를 키우려면 어떻게 해야 할까요?
단순하게 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 일정 크기의 메모리를 더 덧붙이면 되겠지만, 실제로는 다른 데이터가 저장되어 있을 확률이 높습니다.

따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 합니다.
따라서 이런 작업은 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)
    {
        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);
}

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

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

int main(void)
{
    int *list = malloc(3 * sizeof(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);
}

그렇다면, realloc 을 사용하지 않는 첫 번째 코드에서,
int *tmp = malloc(4 * sizeof(int));처럼 임시 메모리를 새로 할당하지 않고
list = malloc(4 * sizeof(int));처럼 기존 메모리를 새로운 메모리로 업데이트 하면 안될까요?

그렇게 하면 이전 메모리 덩어리들이 빠르게 사라지게 됩니다.

list를 새로운 메모리 덩어리를 저장하도록 바꾸게 되면 기존의 메모리 덩어리는 어디로 갈까요?

컴퓨터 어딘가에 떠다니고 있을 겁니다.
하지만 그 곳을 가리키는 포인터는 아무것도 없게 되죠. 그 곳을 가리키는 화살표의 개념이 더 이상 남아있지 않은 것입니다.

이것이 바로 우리가 임시 변수를 하나 만들어서 기존에 할당한 메모리를 놓치지 않도록 해야 하는 이유입니다.

임시 메모리 변수를 할당(int *tmp = malloc(4 * sizeof(int));)하지 않고 
기존의 메모리 변수에 재할당(list = malloc(4 * sizeof(int));)하게 되면,
기존의 메모리들이 가리키는 주소값이 사라지는 오류가 생깁니다. 

이는 메모리는 여전히 남아있지만 접근 방법은 존재하지 않는 다는 점에서 문제가 됩니다.

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기