링크드 리스트의 주요 연산 - 노드의 생성과 소멸

링크드 리스트의 주요 연산 - 노드의 생성과 소멸

이전 포스팅에서 기본적으로 링크드 리스트를 구축하고 링크드 리스트에 있는 자료를 사용하기 위해 필요한 연산은 다음 다섯 가지라고 설명했습니다.

1. 노드 생성/소멸
2. 노드 추가
3. 노드 탐색
4. 노드 삭제
5. 노드 삽입

노드 생성/소멸

C언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가집니다. 하나는 전역 변수나 정적 변수 등이 저장되는 정적 메모리(Static Memory)이고, 또 다른 하나는 지역 변수가 저장되는 자동 메모리(Automatic Memory), 그리고 마지막 하나는 자유 저장소(Free Store)입니다.

정적 메모리는 프로그램이 실행되면서 프로그램에서 사용될 전역 변수/정적 변수를 메모리에 할당한 후 프로그램이 종료될 때 해제하는 영역이기 때문에 일단 머릿 속 한 쪽에 잘 보관해 두기만 하면 됩니다. 혹시 잊어버리더라도 큰 문제가 되지는 않습니다. 하지만 프로그래머라면 자동메모리와 자유 저장소에 끊임없이 관심을 가져야 하기는 합니다. 포인터를 모르는 Java 프로그래머라고 할 지라도 말입니다. Java의 경우 가비지 컬렉터가 자동으로 자유 저장소를 관리해주지만, 프로그래머가 가비지 컬렉터의 속성을 모르는 경우 메모리 누수를 만드는 경우가 종종 발생하기도 하기 때문입니다.

자동 메모리는 스택 구조로 이루어져 있어 이곳에 저장된 변수는 코드 블록('{'와'}'의 괄호로 이루어진 블록)이 종료됨에 따라 사라집니다. 예를 들어 다음과 같이 코드 블록 안에서 선언된 변수들은 선언 당시에 자동 메모리에 저장되었다가 코드 블록의 끝에서 모두 제거됩니다.

{    /* 코드 블록 시작*/
    int a = 37;
    Node MyNode;
}    /* 코드 블록 끝. 여기에서 a와 MyNode는 자동메모리에서 제거된다. */

그리고 이 규칙은 함수에도 동일하게 적용됩니다.

int Plus ( int a, int b )    /* a와 b도 자동 메모리에 저장된다. */
{
    int c = a + b;            /* c도 물론 자동 메모리에 저장된다. */
    return c;
}    /* a, b, c 모두 자동 메모리에서 제거된다. */

이쯤 되면 자동 메모리가 왜 자동 메모리인지는 이해가 되실 것입니다. 코드 블록이 끝나는 곳에서 자동으로 메모리를 해제하기 때무에 그런 이름이 붙여진 것입니다.

자유 저장소는 자동 메모리와는 달리 프로그래머가 직접 메모리를 관리하는 메모리 영역입니다. 자유 저장소의 '자유'는 자동 메모리 영역에서 코듣 블록이라는 한계로부터의 해방을 의미합니다. 그러나 프로그래머는 그 메모리를 안전하게 해제하는 것에 대한 '책임'을 져야 한다는 점을 유의해야 합니다.

그럼 노드의 생성과 소멸에 대한 이야기로 돌아가서, 노드는 자동 메모리와 자유 저장소 중 어느 곳에 생성하는 것이 적절할까요?

먼저 자동 메모리에 노드를 생성하는 것을 고려해봅시다. 다음은 자동 메모리에 노드를 생성하는 함수입니다. 문제가 있는지 찾아보세요.

/* 노드 생성 (문제 버전) */
Node* SLL_CreateNode( int NewData )
{
    Node NewNode; /* 자동 메모리에 새로운 노드 생성 */
    NewNode.Data = NewData;
    NewNode.NextNode = NULL;

    return &NewNode; /* NewNode가 생성된 메모리의 주소를 반환 */
}    /* 함수가 종료되면서 NewNode는 자동 메모리에서 제거된다. */

...
Node* MyNode = SLL_CreateNode(117);    /* MyNode는 할당되지 않은 메모리를 가리킨다. */

문제가 어디에 있는지 보이나요? SLL_CreateNode() 함수 내에서 생성된 NewNode는 함수가 종료하면서 자동 메모리에서 제거됩니다. 하지만 SLL_CreateNode() 함수는 NewNode가 '존재했던' 메모리의 주소를 반환합니다. 따라서 MyNode 포인터는 잘못된 메모리를 가리키고 프로그램은 죽어버리거나 엉뚱한 동작을 하게 될 것입니다.

자동 메모리를 사용할 수 없다는 것을 알았으니 남은 답안은 자유 저장소 밖에 없습니다. 자유 저장소에 메모리를 할당하려면 malloc() 함수가 필요합니다.

void* malloc( size_t size );

malloc() 함수의 반환형인 void* 는 '만능 포인터'입니다. 어떤 형이라도 가리킬 수 있습니다. 이는 곧 malloc() 함수가 할당한 자유 저장소의 메모리 주소르르 어떤 형의 포인터로도 가리킬 수 있다는 것을 의미합니다. 그리고 malloc() 함수의 유일한 매개 변수의 자료형이자 sizeof 연산자의 반환형이기도 한 size_t는 typedef문을 이용하여 unsigned int의 별칭으로 선언되어 있습니다. 간단히 말하여 size_t는 곧 unsigned int 형이라는 말입니다.

malloc() 함수를 사용하여 노드를 자유 저장소에 생성하는 예제는 다음과 같습니다.

Node* NewNode = (Node*)malloc(sizeof(Node));

위 예제에서 malloc() 함수는 sizeof 연산자가 측정한 노드의 크기만큼 자유 저장소에 할당한 후, NewNode에 그 메모리 주소를 저장합니다. 그러면 이번에는 malloc()을 이용하여 SLL_CreateNode()함수가 제대로 동작할 수 있도록 코드를 고쳐보겠습니다.

/* 노드 생성 */
Node* SLL_CreateNode(ElementType NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));

    NewNode->Data = NewData;    /* 데이터를 저장한다. */
    NewNode->NextNode = NULL;    /* 다음 노드에 대한 포인터는 NULL로 초기화한다. */

    return NewNode;                /* 노드의 주소를 반환한다. */
}

노드를 소멸시키는 방법은 간단합니다. 자유 저장소의 해결사인 free() 함수가 노드가 있는 주소를 정확히 알려주기만 하면 뒷일은 모두 free() 함수가 알아서 처리합니다.

void free(void * memblock);

다음은 노드를 소멸하는 SLL_DestroyNode() 함수입니다. 노트가 존재하는 주소를 가리키는 포인터를 free() 함수에게 넘겨 노드를 소멸시킵니다.

/* 노드 소멸 */
void SLL_DestroyNode(Node* Node)
{
    free(Node);
}

※ SLL_의 의미?
SLL 은 Singly Linked List의 약자입니다. 더블 링크드 리스트의 노드들이 양쪽 방향으로 서로 엮여있는 반면, 링크드 리스트는 한쪽 방향으로만 엮여있기 때문에 'Singly'라는 수식어를 붙여 구분을 한 것입니다. 즉, 더블드 링크드 함수의 경우에는 DLL_이라는 접두어를 붙일 수 있습니다.

 

 

이것은 네이버로 연결되는 링크