[C] 단순 연결 리스트 (Single Linked List) 1. 정의 / 생성 / 소멸

 단순 연결 리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킨다.

(참고 : http://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8)

 

 단순 연결 리스트는 "연결 리스트 (Linked List) 정의" 에서 예로 든 것과 같이 꼬리에 꼬리를 무는 방식으로 메모리를 활용하여 데이터를 저장하는 방식이다.

 사용하는 메모리에 모두에 대한 주소값을 저장할 필요없이 가장 첫번째 노드(Head) 에 대한 주소값만 저장하고 있으면, 필요에 따라 꼬리에 꼬리를 물어가며 필요한 데이터를 찾을 수 있다.

 

 다음과 같이 단순 연결 리스트의 구조체를 선언하였다.

 단순 연결 리스트는 자료 공간과 한 개의 포인터 공간으로 나누어 생각할 수 있는데, 여기에서는 단순하게 자료 공간은 정수형(int) 자료 공간 하나만을 가지고 구현하고, 설명한다. DATA_TYPE unData 는 정수형 자료 공간을 가지게 되며, SLL *pstNextSLL 은 다음 노드를 가리킬 포인터 공간이다.

 

 가장 먼저 노드의 생성 함수를 만들었다.

 ifCreateSLL 함수는 return "i"(Integer) "f"(Function) "Create" "SLL"(Single Linked List) 이라는 의미로 명명하였다. 저장하고자 하는 데이터를 받아와서, 한개의 노드에 필요한 메모리를 할당한 후, 데이터를 저장하고, 생성한 노드의 주소를 저장한다. 사용할 때는 다음과 같이 포인터 변수를 선언하고, 함수에 포인터의 주소와 데이터를 매개변수로 넘기면 새로운 만들어진 노드의 주소가 매개변수로 넘긴 포인터에 저장된다.

 

 다음으로는 메모리를 할당한 노드의 사용이 끝났을 때, 해당 메모리를 반환하는 함수이다.

 ifDestorySLL 함수는 return "i"(Integer) "f"(Function) "Destory" "SLL" 이라는 의미로 명명하였다. free 함수는 포인터가 가리키고 있는 메모리 영역을 다시 힙 영역으로 돌리는 역할을 한다. 한번 메모리 영역을 되돌리면 다시 사용할 수 없다.

 

 다음은 마지막으로 단순 연결 리스트로 연결된 모든 노드의 메모리를 반환하는 함수이다.

 가장 처음 노드(Head) 부터, 꼬리에 꼬리를 무는 방식으로 연결된 모든 노드의 메모리를 반환한다. 다음 노드의 포인터를 계속해서 임시로 저장해가며, 노드들의 메모리를 반환한다.

 

 리스트는 배열과 달리 동적으로 메모리를 할당하여 사용할 수 있다는 장점이 있는 대신에, 사용하는 메모리를 효율적으로 사용하고, 반환해야할 필요성이 생긴다. 프로그램에서 메모리를 할당하고, 사용하지 않는 메모리를 반환하지 않는다면, 지속적으로 메모리 누수가 생겨 시스템이 더 이상 동작할 수 없게 될 수도 있다.