[C] 원형 연결 리스트 (Circular Linked List) 1. 정의 / 생성 / 소멸

 원형 연결 리스트는 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조이다.

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

 

 원형 연결 리스트는 메모리를 활용하여 데이터를 저장하는 방식이 이중 연결 리스트와 같다. 하지만, 이중 연결 리스트와 다른 점은 리스트의 첫번째 노드의 앞 노드를 가리키는 포인터가 마지막 노드를, 마지막 노드의 다음 노드를 가리키는 포인터가 첫번째 노드를 가리킨다는 점이다. 이는 이중 연결 리스트보다 이해하는 데에, 그리고 구현하는 데에 어려움을 준다. 반면, 리스트에 노드를 추가할 때의 수행 시간이 O(n) 에서 O(1) 로 줄어든다는 장점이 있다.

 그 밖에 메모리를 사용 등 모든 것은 이중 연결 리스트와 동일하다.

 

 다음은 원형 연결 리스트의 선언이다.

 이중 연결 리스트와 같다. 여기에서는 단순 연결 리스트를 설명할 때와 마찬가지로 자료 공간은 정수형(int) 자료 공간 하나만을 가지고 구현하고, 설명한다.

 

 다음은 노드의 생성 함수, 메모리를 할당한 노드의 사용이 끝났을 때, 해당 메모리를 반환하는 함수, 원형 연결 리스트로 연결된 모든 노드의 메모리를 반환하는 함수이다.

 이중 연결 리스트와 리스트로 연결된 모든 노드의 메모리를 반환하는 함수에서 다른 점이 있다. 이중 연결 리스트에서는 리스트의 마지막 노드의 다음 노드를 가리키는 포인터가 NULL 이었기 때문에, 함수의 끝이 명확하였지만, 원형 연결 리스트에서는 포인터가 항상 특정 메모리 주소를 가리키게 되기 때문에 함수의 끝이 명확하지 않다.

 포인터는 특정 주소를 가지고 있으므로, 이미 반환된 메모리라도, 주소값은 이전과 동일하다. 그러므로, pstInCDLL_Head 가 가리키고 있었던, 리스트의 첫번째 노드가 이미 메모리가 반환이 되었다고 해도, pstCDLL_Temp_1 != pstInCDLL_Head 와 같이 비교할 수 있다. 자세한 설명 및 사용에 관련된 사항은 이전 글 (링크 : [C] 단순 연결 리스트 (Single Linked List) 1. 정의 / 생성 / 소멸) 에서 확인할 수 있다.