연결 리스트 3-1

원형 연결 리스트 

 

 

계속해서 연결 리스트에 관해 알아보자. 

 

원형 연결 리스트 

 

단순 연결 리스트의 마지막 노드 tail은 NULL 을 가리킨다. 

그러나 원형 연결 리스트는 마지막 노드는 첫번째 노드를 가리킨다. 

그래서 원형을 띄고 있기에 원형 연결 리스트인 것이다. 

 

새 노드의 추가 

 

사실 노드들이 원형으로 연결되어 있기에, 머리와 꼬리의 구분이 명확하지 않으며 

우리는 꼬리를 가리키는 포인터 변수만 존재해도 꼬리에 노드를 추가할 수 있다. 

plist->head = plist->tail->next;

이제 

원형 연결 리스트에서 새로운 노드를 추가하는 방법은 다음과 같다. 

 

• LInsert // 꼬리에 삽입
• LInsertFront // 머리에 삽입 

 

더미노드가 존재하지 않기에 당연히 첫 노드와 두번째 이후의 노드의 추가 방법은 구분된다.

 

1. 첫 번째 노드에 새 노드 추가 
2. 두 번째 노드 이후의 새 노드 추가 

 

그런데 여기서도 머리에 추가, 꼬리에 추가 세부항목으로 나뉜다. 

 

 

우선 첫 번째 노드에 새 노드를 추가하는 방법을 알아보자. 

 

첫 번째 노드는 머리이자 꼬리라고 볼 수 있기에 새 노드를 어디에 추가해도 동일한 결과가 나타난다. 

 

if(plist->tail == NULL)
{
	plist->tail = newNode;
    newNode->next = newNode;
}

 

 

두 번째 이후의 노드 추가에 관해 살펴보자

 

- 머리에 삽입 

 

newNode->next = plist->tail->next;
plist->tail->next = newNode;

 

새 노드의 다음은 원래 연결되어 있던 꼬리의 다음으로 노드를 연결해 준다. 

그다음 꼬리와 새 노드를 연결해 준다. 

 

- 꼬리에 삽입 

 

newNodew->next = plist->tail->next;
plist->tail->next = newNode;
plist->tail = newNode;

 

 

원형 연결 리스트의 나머지 구현 

 

이제 원형 연결 리스트의 조회, 삭제에 관해 알아보자. 

 

• LFirst 

단순 연결 리스트와 동일하게 cur, before 을 사용한다. 

 

plist->before = plist->tail;
plist->cur = plist->tail->next;

 

 

 

• LNext

plist->before = plist->cur;
plist->cur = plist->cur->next;

 

cur, before 함수를 다음 노드로 이동하는 것이다. 

 

 

 

• LRemove

노드 삭제는 두 가지 예외 상황을 고려해야 한다. 

 

- tail이 삭제할 노드를 가리키는 경우 

- 위의 경우에 그 노드가 마지막 노드인 경우 

 

if(rpos == plist->tail)
{   
    if(plist->tail == plist->tail->next)
    	plist->tail = NULL;
    else
    	plist->tail = plist->before;
}

plist->before->next = plist->next;
plist->cur = plist-->before;