[SW 정글 35일차] 동적 메모리 할당 (링크드리스트, 이진탐색트리)

오늘은 C언어를 배우고 c언어를 이용해서 연결리스트, 이진탐색트리를 구현하면서 상용한 동적 메모리 할당과 잘못 사용하면 발생할 수 있는 메모리 누수에 대해 정리해보려고 한다.

 

우리는 배열을 배우면서 우리가 데이터를 저장하고자 할 때 필요한 메모리의 양을 확정적으로 알려줘야 했다.

그 이유는 우리가 정적으로 생성하는 배열은 메모리 영역 중 stack 영역의 메모리에 저장되고 stack에서 메모리는 컴파일 시점에 결정된다.

즉, 사용자가 '이만큼 원해요'를 컴파일러에게 반드시 알려줘야한다는 것이다.

아래의 그림은 메모리 구조이다.

 

정적으로 메모리 할당을 해야한다면 항상 고정적으로 메모리의 양을 알려줘야하기때문에 비효율적인 경우가 생길 수 있다.

그냥 그때 그때 우리가 원하는 만큼만 받아서 사용하면 편리할텐데...

그래서 나온 것이 동적 메모리 할당이다.

 

동적 메모리 할당은 기존에 우리가 배열을 생성할 때 아래와 같이 '몇 바이트의 공간이 필요해'라고 명시해주는 것이 아닌 내가 원하는 만큼의 양이 가변적으로 변할 수 있다는 것이다.

위에서 말한 정적으로 할당하는 메모리 공간은 stack영역에 할당되지만 동적으로 할당받은 메모리 공간은 힙 영역에 할당받는다.

힙 영역은 스택영역과 달리 실행시점(run time)에 결정되기 때문에 사용자가 미리 알려주지 않아도 문제가 되지 않는다.

그러면 동적 메모리 할당은 어떻게 해야하는 것일까?

먼저, 코드를 봐보자.

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

void matin()
{
  int SizeOfArray;
  int *arr;
  scanf("%d", &SizeOfArray);
  arr = (int *)malloc(sizeof(int) * SizeOfArray);
  free(arr);
}

위 코드를 보면 새롭게 접하는 malloc이라는 함수가 있다.

malloc은 memory allcoation의 약자로 <stdlib.h> 라이브러리에 내제된 함수이고 이 함수는 인자로 전달된 크기의 바이트 수만큼 메모리 공간을 만드는 기능을 한다.

그러면 위 코드를 보면 arr이라는 배열은 int형 배열인데 메모리의 크기가(int의 크기(4바이트)) * (sizeofArray)만큼 할당받게 되는 것이다.

여기서, sizeof(int)는 int 타입의 크기를 알려주는 기능을 하는 것이고 malloc함수 앞에 붙은 (int *)는 형변환을 위해 쓰인 것이다.

할당을 받고 다 쓴 메모리는 반납을 해줘야하는데 이 기능을 하는 것이 free()함수이다.

우리가 메모리를 다 쓰고도 free()를 해주지 않고 그대로 차지하고 있다고 자원 상 매우 비효율적이고 free()를 제대로 해주지 않는 다면 메모리 누수(memory leak)가 발생하게 된다.

 

 

 

아래의 코드들은 어제부터 구현을 시작한 링크드 리스트와 이진탐색트리 코드이다.

이진탐색트리에 대한 정리는 내일 레드블랙트리와 함께 정리하고 링크드 리스트대한 정리 내용은 예전에 정리한 적이 있어 링크를 걸고 마무리하려고 한다.

https://straw961030.tistory.com/211

[SW 정글 28일차] 연결리스트 만들어보기

파이썬으로 둘 다 한번씩 구현해봤는데 C언어로 하니까 뭔가 색다른 느낌이고 pointer를 쓰니까 개인적인 생각으로 더 직관적으로 느껴져서 좋았다.

 

[링크드 리스트 구현 코드]

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

typedef struct NODE
{
    struct NODE *next;
    int data;
}node;

void addFirst(node *target, int data) 
{
    if (target == NULL)
        return;
    node *newnode = malloc(sizeof(node));
    if (newnode == NULL)
        return;
    newnode->next = target->next;
    target->next = newnode->next;
    newnode->data = data;
}

//기준 노드 다음 노드를 삭제
void removeFirst(node *target) {
    if (target == NULL)
        return;

    node *removenode = target->next;
    if (removenode == NULL)
        return;
    target->next = removenode->next;
    free(removenode);
}

// 특정 노드 검색
node *findNode(node *Node, int data)
{
    if (Node == NULL)
        return NULL;
    node *curr = Node->next;
    while(curr != NULL) {
        if (curr->data == data)
            return curr;
        curr = curr->next;
    }

    return NULL;
}

// 특정 노드 삭제
node *removeNode(node *Node, int data)
{
    if (Node == NULL)
        return NULL;
    node *curr = Node;
    node *prev = NULL;
    while(curr != NULL)
    {
        if (curr->data == data)
            prev->next = curr->next;
            free(curr);
        prev = curr;
        curr = curr->next;
    }

    return NULL;
}

 

 

[이진탐색트리 구현 코드]

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

typedef struct NODE
{
    int data;
    struct NODE *leftchild;
    struct NODE *rightchild;
} node;

// create new BST tree
node *newBST(int data)
{
    node *tmp = malloc(sizeof(node));
    tmp->data = data;
    tmp->leftchild = tmp->rightchild = NULL;
    return tmp;
}

// traversal of BST(시간복잡도:O(n))
void inorder(node *root)
{
    if (root != NULL)
    {
        inorder(root->leftchild);
        printf("%d\n", root->data);
        inorder(root->rightchild);
    }
}

// search node
node *search(node *root, int data)
{
    if (root==NULL || root->data == data)
        return root;
    
    else if (root-> data > data)
        return search(root->leftchild, data);

    else
        return search(root->rightchild, data);
}

// insert new node to BST tree
node *insert(node *root, int data)
{
    if (root == NULL)
        return newBST(data);

    else
    {
        if(root->data > data)
            root->leftchild = insert(root->leftchild, data);
        else
            root->rightchild = insert(root->rightchild, data);
    }
    return root;
}

// find minVal in BST
node *minValueNode(node *Node)
{
    node *current = Node;
    while(current && current->leftchild != NULL)
        current = current->leftchild;
    
    return current;
}

// find maxVal in BST
node *maxValueNode(node *Node)
{
    node *current = Node;
    while(current && current->rightchild != NULL)
        current = current->rightchild;
    
    return current;
}

// delete node in BST
node *deleteNode(node *root, int data)
{
    if (root==NULL)
        return root;
    
    if (data < root->data)
        root->leftchild = deleteNode(root->leftchild, data);

    else if (data > root->data)
        root->rightchild = deleteNode(root->rightchild, data);

    else {
        // node with only one child or no child
        if (root->leftchild == NULL) {
            node *temp = root->rightchild;
            free(root);
            return temp;
        }

        else if (root->rightchild == NULL) {
            node *temp = root->leftchild;
            free(root);
            return temp;
        }

        // node with two childs
        node *temp = minValueNode(root->rightchild);
        root->data = temp->data;
        root->rightchild = deleteNode(root->rightchild, temp->data);
    }
    return root;
}

---

[오늘의 나는 어땠을까?]

오늘은 계획한 바로는 컴퓨터시스템 책을 읽으면서 c언어를 공부하면서 접한 cs지식의 깊이를 더 깊게 하고자 했는데 이진탐색트리 구현과 링크드 리스트 구현이 더 재미있어서 책을 많이 읽지 못했다.

내일부터는 목표량을 정해서 읽으려고 하는데 일단은 red-black tree가 우선이여서 고민이 된다.

 

정글에 들어오기 전에는 스택, 큐정도만 알고있던 내가 트리, 링크드리스트, 우선순위 큐와 같은 기본 자료구조와 red-black tree라는 고급 자료구조까지 공부를 하고 있다.

이렇게 보면 내가 성장했다는 것을 느낄 수 있다.

이러한 성장속도가 나의 무기가 되었으면 좋겠고 이 무기를 인정받아 개발자로서의 커리어를 시작하고 싶다.

 

이전부터 동료들에게 가끔씩 들어온 말이지만 나에게 '열심히 한다', '의지가 대단하다' 등 나의 생활패턴과 노력에 자극을 받는 동료들이 있었다.

나로서는 너무 좋고 감사한 일이다.

나는 인정해줘서 좋은 것이 아니라 같은 환경에 있고 같은 목표를 가지고 성장하는 동료로서 나로부터 좋은 자극을 받고 더 성장하기 위해 노력하려고 하는 것이 좋다.

정말 다 같이 수료 후에 원하는 목표를 이루었으면 좋겠고 개발자로서의 커리어를 시작했으면 하는 바램이 있다.

 

앞으로 계속해서 함께 성장하기를 바라고 상호작용하며 낙오자없이 정글을 마무리했으면 좋겠다.

---

<참고 자료>

https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/

https://modoocode.com/98

https://dojang.io/course/view.php?id=2 

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EB%A6%AC_%EB%88%84%EC%88%98