원형 연결 리스트 (Circular Linked List)

맨 마지막 노드의 포인터가 다시 첫 노드를 가리키는 연결 리스트 구조이다. 

단순 연결 리스트에서는 이전에 위치한 노드를 탐색할 수 없다.

원형 연결 리스트에서는 이전 노드까지 계속 반복문을 돌다 보면 이전 노드에 도착할 수 있어서 편리하다. 

목적지까지 한 번만 운행하는 열차와, 같은 구간을 도는 순환 열차를 생각하면 되겠다.

이번에는 헤드 포인터(Head pointer)를 사용해서 구현하는 법을 정리해 보겠다.

참고로 헤드 포인터란, 원형 연결 리스트 구조체 안에서 노드를 가리키는 포인터이다.

원형 연결 리스트는 맨 마지막 노드가 첫번째를 가리킨다는 조건이 있으므로, 노드의 삽입과 삭제 기능을 구현할 때 주의 해야 한다.

※ 밑에 헤드 포인터의 타입은 CircularListNode* 임. 현재 그림에 CircularList*라고 되어 있는데 오타임.

1) 노드 추가하기 (Node Add)

---

리스트를 추가 할 때는 4가지의 경우가 있다.

1. 첫 번째 노드로 추가할 때 (헤드 포인터가 가리키는 노드가 없는 경우, 즉 리스트가 완전히 비어 있는 경우) 

헤드 포인터에 연결된 노드가 하나 존재하므로, 이 연결된 노드는 첫 번째 노드이자 마지막 노드가 된다. 결국 자기 자신을 가리키는 모양이 된다.

2. 첫 번째 위치에 삽입할 때 (헤드 포인터가 가리키는 노드가 있는 경우, 기존에 연결된 리스트가 존재 하는 경우)

3개의 노드가 연결 되어 있는 상태에서 첫 번째 위치에 노드를 삽입 한다고 생각해 보자.

보라색 점선은 newNode가 추가되기 전 마지막 노드가 가리키고 있던 것을 의미한다. 지금은 새로운 첫번째 노드가 연결 되었으니 새로 이어준다.

3. 중간에 노드를 삽입할 때

단순 연결 리스트와 동일하다. ⅰ이전 노드가 새로운 노드를 가리키고, ⅱ 새로운 노드가 이전 노드가 원래 가리키던 곳을 가리키게 설정한다.

4. 마지막에 노드를 삽입할 때 

마지막에 노드를 삽입하면, 새로운 노드가 가리키는 곳은 첫 번째 노드로 설정되고, 이전에 가리키던 노드가 가리키는 곳은 새로운 노드가 된다.

2) 노드 삭제하기 (Node Delete)

---

1. 첫번째 노드이면서 마지막 노드인 경우

노드가 하나만 존재하는 경우이다. 구조체를 메모리에서 해제 시켜준 후에 헤드포인터를 NULL로 설정한다.

2. 첫번째 노드이면서 다른 노드와 연결되어 있는 경우

ⅰ 헤드 포인터의 노드를 첫 번째 노드가 가리키는 노드로 재 설정하고, ⅱ 마지막 노드가 가리키는 노드를 첫 번째 노드가 가리키는 곳으로 설정한다.

그리고 첫번째 노드를 메모리 해제 시켜주면 끝.

3) 마지막 노드를 삭제할 때

마지막 노드 이전의 노드가 첫 번째 노드를 가리키게 설정하고 메모리 해제 시킨다.

코드는 추후 업로드 예정입니다.