CS | 자료구조(1) - malloc 과 포인터 복습, 배열의 크기 조정, 연결 리스트 [도입, 코딩]

아래와 같은 main 함수 코드가 있다.

여기서 문제가 될 만한 지점이 있는데...

 

int main(void)
{
    int *x;
    int *y;

    x = malloc(sizeof(int));

    *x = 42;
    *y = 13;
}

main 함수 안의 첫 두 줄에서는 포인터 x와 y를 선언한다.

그리고 x에는 malloc 함수를 이용해서 int 자료형 크기에 해당하는 메모리를 할당한다.

그 다음에는 x와 y 포인터가 가리키는 지점에 각각 42와 13을 저장한다.

여기서 문제가 될 만한 부분은 *y = 13 이다.

y는 포인터로만 선언되었을 뿐이지, 어디를 가리킬지에 대해서는 아직 정의가 되지 않았다.

따라서 초기화 되지 않은 *y는 프로그램 어딘가를 임의로 가리키고 있을 수도 있다.

따라서 그 곳에 13이라는 값을 저장하는 것이 오류를 발생시킬 수도 있는 것이다.

 

아래 코드와 같이 y = x; 라는 코드를 더해주면,  y는 x가 가리키는 곳과 동일한 곳을 가리키게 된다.

따라서 *y = 13; 으로 저장하면  x가 가리키는 곳에도 동일하게 13으로 저장될 것이다.

 

y = x;

*y = 13;

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

단순하게 현재 배열이 저장되어 있는 메모리 위치의 바로 옆에 일정 크기의 메모리를 더 덧붙이면 되겠지만,

실제로는 다른 데이터가 저장되어 있을 확률이 높다.

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

따라서 이런 작업은 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);
}

---

데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체이다.

일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있다.

 

배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.

하지만 굳이 그럴 필요는 없다.

각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도

바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수 있다.

이를 ‘연결 리스트’라고 한다.

아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.

 

 

연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장하고 있다.

3은 다음 값이 없기 때문에 NULL (\0, 즉 0으로 채워진 값을 의미합니다)을 다음 값의 주소로 저장한다.

 

연결 리스트는 아래 코드와 같이 간단한 구조체로 정의할 수 있다.

typedef struct node
{
    int number;
    struct node *next;
}
node;

node 라는 이름의 구조체는 number 와 *next  두 개의 필드가 함께 정의되어 있다.

number는 각 node가 가지는 값, *next 는 다음 node를 가리키는 포인터가 된다.

여기서 typedef struct 대신에 typedef struct node 라고 ‘node’를 함께 명시해 주는 것은,

구조체 안에서 node를 사용하기 위함이다.

 

앞서 정의한 구조체를 활용해서 실제로 연결 리스트를 구현해보도록 하자.

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

//연결 리스트의 기본 단위가 되는 node 구조체를 정의합니다.
typedef struct node
{
    //node 안에서 정수형 값이 저장되는 변수를 name으로 지정합니다.
    int number; 

    //다음 node의 주소를 가리키는 포인터를  *next로 지정합니다.
    struct node *next;
}
node;

int main(void)
{
    // list라는 이름의 node 포인터를 정의합니다. 연결 리스트의 가장 첫 번째 node를 가리킬 것입니다. 
    // 이 포인터는 현재 아무 것도 가리키고 있지 않기 때문에 NULL 로 초기화합니다.
    node *list = NULL;

    // 새로운 node를 위해 메모리를 할당하고 포인터 *n으로 가리킵니다.
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number 필드에 1의 값을 저장합니다. “n->number”는 “(*n).numer”와 동일한 의미입니다. 
    // 즉, n이 가리키는 node의 number 필드를 의미하는 것입니다. 
    // 간단하게 화살표 표시 ‘->’로 쓸 수 있습니다. n의 number의 값을 1로 저장합니다.
    n->number = 1;

    // n 다음에 정의된 node가 없으므로 NULL로 초기화합니다.
    n->next = NULL;

    // 이제 첫번째 node를 정의했기 떄문에 list 포인터를 n 포인터로 바꿔 줍니다.
    list = n;

    // 이제 list에 다른 node를 더 연결하기 위해 n에 새로운 메모리를 다시 할당합니다.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    // n의 number와 next의 값을 각각 저장합니다.
    n->number = 2;
    n->next = NULL;

    // list가 가리키는 것은 첫 번째 node입니다. 
    //이 node의 다음 node를 n 포인터로 지정합니다.
    list->next = n;

    // 다시 한 번 n 포인터에 새로운 메모리를 할당하고 number과 next의 값을 저장합니다.
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }

    n->number = 3;
    n->next = NULL;

    // 현재 list는 첫번째 node를 가리키고, 이는 두번째 node와 연결되어 있습니다. 
    // 따라서 세 번째 node를 더 연결하기 위해 첫 번째 node (list)의 
    // 다음 node(list->next)의 다음 node(list->next->next)를 n 포인터로 지정합니다.
    list->next->next = n;

    // 이제 list에 연결된 node를 처음부터 방문하면서 각 number 값을 출력합니다. 
    // 마지막 node의 next에는 NULL이 저장되어 있을 것이기 때문에 이 것이 for 루프의 종료 조건이 됩니다.
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

    // 메모리를 해제해주기 위해 list에 연결된 node들을 처음부터 방문하면서 free 해줍니다.
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}