[알고리즘] Linked List ( 노드 생성 / 소멸 )

Linked List의 주요 연산

• 노드 생성 / 소멸

C언어로 작성된 프로그램은 세 가지 종류의 메모리 영역을 가집니다.

정적 메모리(Static Memory) / 자동 메모리( Automatic Memory)/ 자유 저장소(Free Store)

 

 

정적 메모리 

- 프로그램이 실행하면서 프로그램에서 사용될 전역 변수/정적 변수를 메모리에 할당한 후 프로그램이 종료될 때 해체하는 영역

 

 

자동 메모리

- 스택 구조로 이루어져 있어 이곳에 저장된 변수는 코드 블록이 종료됨에 따라 사라집니다.

코드블록 안에서 선언된 변수들은 선언 당시에 자동 메모리에 저장되었다가 코드 블록의 끝에서 모두 제거됩니다.

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

/* 함수 */
int Plus(int a, int b)
{
	int c = a + b;
    return c;
}/* a,b,c 모두 자동 메모리에서 제거된다. */

코드 블록이 끝나는 곳에서 자동으로 메모리를 해제하기 때문에 자동메모리입니다.

 

 

자유 저장소

- 자동 메모리와는 달리 프로그래머가 직접 메모리를 관리하는 메모리 영역입니다.

프로그래머는 자유롭게 메모리를 할당해서 사용할 수 있지만 그 메모리를 안전하게 해체하는 것도 프로그래머가 책임져야 합니다.

 

 

 

노드는 자동 메모리와 자유 저장소 중 어느 곳에 생성하는 것이 적절할까요 ?

1. 자동 메모리를 선택했을 때 :

새로운 노드를 자동 메모리에 생성했을 때, 함수가 종료하면서 자동 메모리에서 제거 됩니다.

함수에 새로운 노드가 '존재했던' 메모리의 주소를 반환합니다. (엉뚱한 메모리를 가리킴)

 

2. 자유 저장소를 선택했을 때 :

자유 저장소에 메모리를 할당하려면 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에 그 메모리 주소를 저장합니다.

 

노드 생성

/* 노드 생성 */
Node* SLL_CreateNode(ElementType NewData)
{
	Node* NewNode = (Node*)malloc(sizeof (Node));
    
    NewNode -> Data = NewData; /* 데이터를 저장 */
    NewNode -> NextData = NULL; /* 다음 노드에 대한 포인터는 NULL로 초기화 */
    
    return NewNode; /* 노드의 주소를 반환 */

}

 

노드 소멸

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

자유 저장소 free() 함수에게 노드가 있는 주소를 정확히 일러주기만 하면 free() 함수가 알아서 처리합니다.

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