[자료구조] 리스트 - (1)링크드리스트(LinkedList)

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

 

1. 전역 변수나 정적변수가 저장되는 정적 메모리(Static Memory) - 데이터 영역

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

2. 지역 변수가 저장되는 자동 메모리(Automatic Memory) - 스택 영역

 - 스택 구조로 이루어져 있어 이곳에 저장된 변수는 코드블록이 종료됨에 따라 자동으로 메모리에서 제거됨.

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

3. 자유저장소(Free Store) - 힙 영역

 - 자동메모리와 다르게 프로그래머가 직접 메모리는 관리하는 메모리 영역.

 

---

 

Q. 여기서 노드는 자동 메모리(스택)와 자유 저장소(힙)중 어느곳에 생성하는 것이 적절할지 생각해보자.

// 자동메모리에 노드를 생성
Node* CreateNode(int NewData)
{
    Node NewNode;        // 자동메모리에 새로운 노드 생성
    NewNode.Data = NewData;
    NewNode.NextNode = NULL;
    
    return &NewNode;	// NewNode가 생성된 메모리의 주소를 반환
} // 함수가 종료되면 NewNode는 자동 메모리에서 제거됨.

.
.
.

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

CreateNode() 함수 안에서 생성된 NewNode는 함수가 종료되면서 자동메모리에서 제거되고,

CreateNode()는 NewNode가 '있었던' 메모리의 주소를 반환한다.

 

MyNode포인터는 엉뚱한 메모리를 반환하고, 그렇게 되면 프로그램이 죽거나 엉뚱한 메모리를 반환하는 결과를 초래할 수 있다.

 

그러므로 노드를 생성할 때는 자동 메모리가 아닌 자유메모리에 할당해야 된다는 뜻이다.

C에서 자유 메모리에 메모리를 할당하려면 malloc() 함수가 필요하다.

// void* 는 어떤 형이라도 가리킬 수 있음.
// malloc() 함수가 할당한 자유 저장소의 메모리 주소를 어떤 형의 포인터로도 가리킬 수 있다.
void* malloc(size_t size)

sizeof 연산자의 반환형 size_t는 typedef문을 이용해서 unsigned int 의 별칭으로 선언되어있음.

size_t는 곧 unsigned int형이다.

 

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

malloc() 함수를 사용해서 노드를 자유저장소(힙 영역)에 생성 하는 예제이다.

 

---

참고 서적 : 뇌를 자극하는 알고리즘