[C] 원형 연결 리스트 (Circular Linked List) 2. 추가 / 탐색 / 삽입 / 삭제

  노드를 리스트에 추가하는 함수, 첫번째 노드부터 특정 위치에 있는 노드를 찾는 함수, 특정 노드의 다음 위치에 새로운 노드를 연결하는 함수이다.

 이중 연결 리스트와 비교하여 노드를 리스트에 추가하는 함수가 다르다. 단순 연결 리스트에 비해 이중 연결 리스트가 노드를 리스트에서 삭제할 때에 추가적인 연산이 필요없듯, 이중 연결 리스트에 비해 원형 연결 리스트는 노드를 리스트에 추가할 때에 추가적인 연산이 필요없다.

 

 아래 그림과 같이 단순 연결 리스트와 이중 연결 리스트에서는 노드를 리스트에 추가하기 위해서 리스트의 마지막 노드를 찾는 O(n) 의 추가적인 연산이 필요하다.

 하지만, 원형 연결 리스트는 아래 그림과 같이, 리스트의 첫번째 노드의 앞 노드를 가리키는 포인터가 이미 리스트의 마지막 노드를 가리키고 있으므로, 이를 찾는 연산이 필요없다. 이는 원형 연결 리스트의 장점이다.

 

 위의 세개의 함수를 사용하는 예제이다.

 먼저, 3개의 노드를 생성한 후에, pstSearchLocationCDLL, ifCreateCDLL, vfInsertAfterCDLL 순서로 수행하여, "1, 2, 4, 3" 의 자료를 가지는 리스트가 만들어진다.

 

 노드를 리스트에서 삭제하는 함수이다.

 이중 연결 리스트와 동일하다.