앞서 우리가 구현한 연결리스트의 마지막 노드는 NULL을 가리켯다. 바로 이 마지막 노드가 첫번째 노드를 가리키게 하면 이것이 바로 '원형 연결리스트'가된다. 즉 단순연결리스트가 다음의 구조라면
head->2->4->6->8->NULL
마지막 노드가 첫번째 노드를 가리켜서 , 연결의 형태가 원을 이루는 다음 구조의 연결리스트를 가리켜 '원형 연결 리스트'라 한다.
head->2->4->6->8->2
그럼 원형 연결리스트의 특성을 더 알기위해서 숫자 1이 저장된 노드를 머리부분에 추가하겠다.
head->1->2->4->6->8->1
이번엔 반대로 원래상태에서 숫자 1이 저장된 노드를 꼬리에 추가해보겠다 .
head->2->4->6->8->1->2
위의 상태를 보면 다음과 같은 사실을 알 수 있다.
"두 연결 리스트 모두 8이 저장된 노드는 1이 저장된 노드를 가리키고, 1이 저장된 새 노드는 2가 저장된 노드를 가리킨다."
이러한 특성 때문에 원형 연결리스트에서는 머리와 꼬리의 구분이 없다고도 이야기 한다.
실제로 위에서 보이는 두 연결리스트의 유일한 차이점은 변수 head가 무엇을 가리키느냐에 있다. 그것을 제외하면 위의 두 연결 리스트는 차이가 없다.
이번에는 2번째와 같이 꼬리에 노드를 추가하는 방법에 대해서 고민해보자. 이를 위해서는 리스트의 꼬리를 가리키는 포인터 변수 tail이 필요하다는 생각이 든다.
하지만 이렇게 되면 원형연결리스트의 장점이 반감되어 버린다. 원형 연결리스트의 장점 중 하나는 다음과 같기 때문이다.
"단순 연결리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다."
즉 우리는 변형된 연결리스트를 구현할 생각이다.
포인터 변수 tail이 없어서 문제라 했던, 연결리스트의 끝에 노드를 추가하는 것을 보자
head->2->4->6->8->1->2
1 = newNode;
위의 과정 상에서 꼬리에 새로운 노드를 추가하는 방법을 고민해보자. head가 가리키는 것은 머리인, 꼬리에 노드를 추가하기 위해서는 head를 시작으로 리스트의 끝을 찾아가는 과정을 거쳐야만 하는 상황이다. 하지만 조금만 변경하면 이야기는 달라진다.
"하나의 포인터 변수가, 머리가 아닌 꼬리를 가리키게한다"
즉 다음과같은 형태가 된다.
2->4->6->8->1->2
head는 1을 가리킴
위의 과정에서는 포인터 변수인 tail이 리스트의 끝을 가리키는 상황이니, 새로운 노드를 리스트의 끝에 추가하는 것은 어렵지 않다 . tail->next가 가리키는 것은 첫번째 노드이니, 이것을 이용하면 리스트의 머리에도 노드를 쉽게 추가할 수 있다. 즉 다음과 같이 생각하면 되는 상황이다.
꼬리를 가리키는 포인터 변수는 ? tail
머리를 가리키는 포인터 변수는 ? tail->next
이렇듯 첫번째 노드와 마지막 노드를 가리키는 포인터 변수가 각각 존재하는 상황이니, 어렵지 않게 머리에 그리고 꼬리에 새로운 노드를 추가할 수 있다.
앞서 구현한 연결리스트에서 의미를 부여하고 싶은 함수를 묻는다면
LFirst, LNext, LRemove 를 선택할 수 있다.
이유는 이들이 연결리스트의 활용가치를 높인 함수들 이기 때문이다. 저장된 데이터를 적절한 방법으로 참조하고 또 삭제할 수 없다면, 그저 저장이 전부였다면 활용가치는 높지 않았을 것이다. 따라서 원형 연결리스트의 구현에도 이 세 함수를 추가할 것이다. 다만 원형 연결 리스트의 구조적 특성상 LNext 함수의 기능을 다음과 같이 조금 변경하고자 한다.
"LNext함수는 무한 반복 호출이 가능하며, 리스트의 끝에 도달한 경우 첫번째 노드부터 다시 조회가 시작된다."
반면 정렬과 관련이 있었던 기능은 제외시킨다. 이는 원형 연결 리스트를 구현하는데 있어서 불필요한 부분을 최소화 하기 위함이다. 끝으로 데이터를 저장하는 함수는 두 개를 정의하고자 한다. 이는 리스트의 머리에 , 그리고 꼬리에 노드를 추가할 수있게 하기 위함이다.
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef struct _node
{
Data data;
struct _node *next;
}Node;
typedef struct _CLL
{
Node * tail;
Node * cur;
Node * before;
int numOfData;
}CList;
typedef CList List;
void ListInit(List *plist);
void LInsert(List *plist, Data data); //꼬리에 노드를 추가
void LInsertFront(List* plist, Data data); //머리에 노드를 추가
int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);
Data LRemove(List *plist);
int LCount(List *plist);
#endif위의 헤더파일에 담긴 내용 대부분이 익숙할 것이다. 다만 데이터의 입력과 관련해서 다음과 같이 두개의 함수가 선언된 점에만 유의해야 한다.
void LInsert(List *plist, Data data); //꼬리에 노드를 추가
void LInsertFront(List *plist, Data data); //머리에 노드를 추가
사실 이렇듯 두 개의 함수를 정의한 이유는 원형 연결리스트의 또 다른 특성을 언급하기 위한 목적도 있다.
변형된 원형 연결 리스트의 구현 1 : 리스트의 초기화와 노드의 삽입
원형 연결 리스트의 초기화는 단순 연결 리스트의 초기화만큼 간단하다. 아래에서 보이는 바와 같이 리스트의 멤버를 NULL 또는 0으로 초기화 하는 것이 전부이다.
void ListInit(List *plist)
{
plist->tail = NULL;
plist->cur = NULL;
plist->before= NULL;
plist->numOfData =0;
}
그럼 위의 함수 호출을 통해서 초기화가 완료된 이후에 첫 번째 노드가 추가되는 상황을 정리해보자.
tail->NULL
2->
>> 추가완료
tail->2->2
이렇듯 tail이 NULL을 가리킨다는 것은 노드가 하나도 추가되지 않았음을 의미한다. 이 상황에서 첫번째 노드가 리스트에 추가되는 과정은 tail이 2를 가리키고 2는 또 자기 자신을 가리키는 것이다.
즉 tail은 새 노드를 가리켜야 하고, 새 노드도 자기자신을 가리켜야 한다.
왜냐하면 처음 추가된 노드는 그 자체로 머리이자 꼬리이기 때문이다.
위 그림에서 보인 첫 번째 노드의 추가 결과는 꼬리에 노드를 추가하는 LInsert 함수의 호출 결과도 되지만, 동시에 머리에 노드를 추가하는 LInsertFront 함수의 호출 결과도 된다. 조금 전에 말했듯이, 첫번째 노드는 그 자체로 머리이자 꼬리이기 때문이다. 따라서 LInsert함수와 LInsertFront함수는 둘다 동일하게 다음과 같은 기본 구성을 갖는다.
void LInsert~(List *plist, Data data) //LInsert & LInsertFront의 공통 부분
{
Node * newNode= (Node *) malloc(sizeof(Node)); //새 노드 생성
newNode->data= data; / 새노드에 데이터 저장
if(plist->tail ==NULL) //첫번째 노드라면
{
plist->tail = newNode; //tail이 새 노드를 가리키게 한다.
newNode->next = newNode; //새 노드 자신을 가리키게 한다.
}
else //두번째 이후 노드라면
{
..차이나는 부분
}
(plist->numOfData)++;
}
이제 위 함수의 빈부분을 채우기 위해서, 두 번째 이후의 노드가 추가되는 상황을 정리해보자.
2와 4가 저장된 연결리스트에 7을 추가하는, 7이 저장된 노드를 리스트의 머리와 꼬리에 각각 추가해보자.
tail이 가리키는 노드가 꼬리에 할당되고, 이 꼬리가 가리키는 노드가 머리에 할당되니, 7이 저장된 새 노드를 머리에 추가하면 다음의 형태가 된다.
4->2->4
tail ->2
>>7추가
7->4->2->7
tail->2
그럼 위 그림의 결과를 얻기 위한 코드를 채워보자
void LInsertFront(List *plist, Data data) //LInsert & LInsertFront의 공통 부분
{
Node * newNode= (Node *) malloc(sizeof(Node)); //새 노드 생성
newNode->data= data; / 새노드에 데이터 저장
if(plist->tail ==NULL) //첫번째 노드라면
{
plist->tail = newNode; //tail이 새 노드를 가리키게 한다.
newNode->next = newNode; //새 노드 자신을 가리키게 한다.
}
else //두번째 이후 노드라면
{
newNode->next= plist->tail->next; //새 노드와 4가 저장된 노드 연결
plist->tail->next= newNode; //2가 저장된 노드와 새노드 연결
}
(plist->numOfData)++;
}
이번엔 7이 저장된 노드를 꼬리에 추가해보자. tail이 가리키는 노드가 꼬리에 해당하니, 7이 저장된 새 노드를 꼬리에 추가하면 다음의 형태가 된다.
4->2->7->4
tail ->7
이번에도 위 그림의 형태가 되는 코드를 넣으면 이것이 LInsert함수가 된다
그런데 else 구문을 채우기에 앞서 머리에 넣는 방법과 꼬리에 넣는 방법을 비교해보자
"노드를 꼬리에 추가했을 때와 머리에 추가했을 떄의 유일한 차이점은 tail이 가리키는 노드가 다르다는 점이다"
즉 새 노드를 머리에 추가한 상태에서 연결 방향을 따라 tail을 한번만 이동시키면, 그 결과가 새노드를 꼬리에 추가한 결과가 된다. 따라서 LInsert 함수의 else구문은 다음과 같이 채울 수 있다.
void LInsert(List *plist, Data data) //LInsert & LInsertFront의 공통 부분
{
Node * newNode= (Node *) malloc(sizeof(Node)); //새 노드 생성
newNode->data= data; / 새노드에 데이터 저장
if(plist->tail ==NULL) //첫번째 노드라면
{
plist->tail = newNode; //tail이 새 노드를 가리키게 한다.
newNode->next = newNode; //새 노드 자신을 가리키게 한다.
}
else //두번째 이후 노드라면
{
newNode->next= plist->tail->next;
plist->tail ->next= newNode;
plist->tail = newNode; //LInsertFront 함수와의 유일한 차이점
}
(plist->numOfData)++;
}
결과를 보면 원형 연결리스트는 머리와 꼬리의 구분이 의미가 없다는 것이 이해가 된다.
변형된 원형 연결 리스트의 구현 2 : 데이터 조회
데이터의 조회를 담당하는 LFirst 함수와 LNext 함수를 구현할 차례이다. 이를 위해서 먼저 다음 구조체의 정의를 보자
typedef struct _CLL
{
Node * tail;
Node * cur;
Node * before;
int numOfData;
}CList;
위 구조체의 멤버 cur과 before의 역할은 단순 연결리스트의 경우와 동일하다. 즉 before는 cur보다 하나 앞선 노드를 가리켜야 하기 때문에, LFirst 함수가 호출되면 이 두 멤버는 각각 다음과 같이 초기화 되어야 한다.
1->2->3->4->5->1
cur->1
tail, before->5
이렇듯 cur과 before이 초기화 되면 LFirst함수는 cur이 가리키는 노드의 데이터를 반환만 하면 된다.
즉 LFirst 함수는 다음과 같이 간단히 정의된다.
int LFirst(List *plist, Data *pdata)
{
if(plist->tail ==NULL) //저장된 노드가 없다면
return FALSE;
plist->before = plist->tail; //before가 꼬리를 가리키게 한다.
plist->cur = plist->tail ->next; //cur이 머리를 가리키게 한다.
*pdata = plist->cur->data; //cur이 가리키는 노드의 데이터 반환
return TRUE;
}
이렇듯 LFirst함수가 호출되면서 cur과 before의 초기화도 이뤄졌으니, 이제 LNext함수가 호출될때 할일은 cur과 before를 한 칸씩 다음 노드로 이동시키는 것이다.
따라서 LNext함수도 다음과 같이 간단히 정의가 된다.
int LNext(List *plist, Data *pdata)
{
if(plist->tail ==NULL) //저장된 노드가 없다면
return FALSE;
plist->before= plist->cur; //before가 다음 노드를 가리키게 한다.
plist->cur= plist->cur ->next; //cur이 다음 노드를 가리키게 한다.
*pdata =plist->cur->Data; //cur이 가리키는 노드의 데이터 반환
return TRUE;
}
참고로 위의 LNext함수에는 리시트의 끝을 검사하는 코드가 존재하지 않는다. 때문에 무한으로 반복해서 호출이 가능하며, 대상이 되는 원형 연결리스트는 머리와 꼬리가 연결된 관계로 리스트의 마지막 까지 조회가 이뤄졌다면, 다시 첫번째 노드에서부터 조회가 시작된다. 즉 위의 LNext함수는 원형 연결 리스트의 특성을 반영해서 구현한 결과라고 할 수 있다.
변형된 원형 연결리스트의 구현 3 : 노드의 삭제
삭제는 대부분의 경우 상대적으로 복잡한 편이다. 하지만 머리와 꼬리가 연결되어 있다는 점만 제외하면, 원형 연결 리스트와 단순 연결리스트는 그 구조가 동일하기 때문에 삭제방법도 유사하다.
그럼 원형 연결리스트의 삭제를 구현하기 위해서 단순 연결리스트의 삭제 과정을 다시 한번 관찰하자.
head->dmy->2->4->6->8->NULL
before->2
cur->4
위의 상태에서 삭제 함수가 실행되면
cur은 before이 위치한 곳으로 이동하게 된다.
핵심연산은 두가지다.
핵심연산1 : 삭제할 노드의 이전 노드가, 삭제할 노드의 다음 노드를 가리키게 한다.
핵심연산2 : 포인터 변수 cur을 한 칸 뒤로 이동시킨다.
그래서 앞서 단순 연결리스트의 삭제 함수는 다음과 같이 정의하였다.
LData LRemove(List *plist)
{
Node *rpos = plist->cur;
LData rdata = rpos->data;
plist->before->next = plist->cur->next; //핵심연산 1
plist->cur= plist->before; //핵심연산2
free(rpos);
(plist->numOfData)--;
return rdata;
}
그런데 이는 원형 연결 리스트라고 해서 달라지지 않는다. 다음 그림에서 보이듯이, 위에서 말한 삭제의 핵심 연산 두가지는 원형 연결 리스트에서도 동일하게 필요하기 때문이다.
1->2->3->4->5->1
tail->5
before->2
cur->3
cur이 before로 이동하고 before이 가리키는 노드를 cur이 가리키던 노드로 변환한다.
따라서 단순 연결 리스트의 LRemove 함수를 그대로 원형 연결 리스트에 사용해도 실제로 삭제가 이뤄지는 것을 확인할 수 있다. 물론 완전하지는 않다.
"단순 연결리스트를 구현할 당시에는 있었던 더미노드가 원형 연결리스트에는 존재하지 않는다."
어쩌면 꼬리와 머리가 연결되어 있는 것을 완전하지 않은 이유로 생각할지도 모르지만, 이는 삭제의 과정에 영향을 미치지 않는다. 영향을 미치는 것은 더미노드가 존재하지 않는다는 사실에 있다.
이렇듯 원형 연결 리스트에는 더미 노드가 존재하지 않기 때문에, 삭제에 있어서 다음 두가지 예외적인 상황을 구분해야 한다.
예외적인 상황1 : 삭제할 노드를 tail이 가리키는 경우
예외적인 상황2 : 삭제할 노드가 리스트에 홀로 남은 경우
예외적인 상황 1에서는 tail이 가리키는 노드가 삭제되므로 tail이 다른 노드를 가리키게 해야한다. 다음 과정에서 보이듯이 삭제될 노드의 이전노드가 tail이 되어야 한다.
반면 예외적인 상황2에서는, 삭제가 진행되고 나면 포인터 변수 tail은 더 이상 가리킬 노드가 존재하지 않으므로 NULL을 가리키게 해야한다. 때문에 이 역시 예외적인 상황으로 분류해야 한다.
따라서 원형 연결 리스트의 LRemove 함수는 위의 두 가지 예외적인 상황의 처리를 포함하여 다음과 같이 정의되어야 한다.
Data LRemove(List *plist)
{
Node *rpos = plist->cur;
Data rdata = rpos->data;
if(rpos==plist->tail) //삭제 대상을 tail이 가리킨다면
{
if (plist->tail == plist->tail->next ) //그리고 마지막 남은 노드라면
plist->tail = NULL;
else
plist->tail= plist->before; //tail을 cur의 이전 노드에 저장
}
plist->before->next = plist->cur->next;
plist->cur= plist->before;
free(rpos);
(plist->numOfData)--;
return rdata;
}
위에서 보이듯이 원형 연결 리스트의 LRemove함수에는, 더미 노드가 있는 단순 연결 리스트의 LRemove 함수에 없었던 if문이 예외적인 상황 둘을 처리하기 위해서 삽입이 되었다.
원형연결리스트에 더미 노드를 붙여주면 LRemove 함수 뿐만아니라, 노드의 추가 와 관련된 두 함수의 구현도 간단해진다. 다만 데이터를 순환 참조하는 LNext함수의 구현에 있어서 더미 노드의 처리를 위한 코드를 추가로 삽입해야 한다는 단점도 생긴다.
이제 원형 연결리스트를 구현해보자.
//CLinkedList.h
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node *next;
}Node;
typedef struct _CLL
{
Node *tail;
Node *cur;
Node *before;
int numOfData;
}CList;
typedef CList List;
void ListInit(List *plist);
void LInsert(List *plist, Data data);
void LInsertFront(List *plist, Data data);
int LFirst(List *plist , Data *pdata);
int LNExt(List *plist, Data *pdata);
Data LRemove(List *plist);
int LCount(List *plist);
#endif//CLinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"
void ListInit(List *plist)
{
plist->tail= NULL;
plist->cur= NULL;
plist->before = NULL;
plist->numOfData =0;
}
void LInsertFront(List *plist, Data data)
{
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if(plist->tail ==NULL)
{
plist->tail= newNode;
newNode->next =newNode;
}
else
{
newNode->next= plist->tail->next;
plist->tail->next= newNode;
}
(plist->numOfData)++;
}
void LInsert(List *plist, Data data)
{
Node* newNode =(Node *)malloc(sizeof(Node));
newNode->data= data;
if(plist->tail ==NULL)
{
plist->tail =newNode;
newNode->next= newNode;
}
else
{
newNode->next= plist->tail->next;
plist->tail->next= newNode;
plist->tail= newNode;
}
(plist->numOfData)++;
}
int LFirst(List *plist, Data *pdata)
{
if(plist->tail ==NULL)
return FALSE;
plist->before= plist->tail;
plist->cur = plist->tail->next;
*pdata= plist->cur->data;
return TRUE;
}
int LNext(List *plist, Data *pdata)
{
if(plist->tail ==NULL)
return FALSE;
plist->before = plist->cur;
plist->cur= plist->cur->next;
*pdata= plist->cur->data;
return TRUE;
}
Data LRemove(List *plist)
{
Node* rpos = plist->cur;
Data rdata = rpos->data;
if(rpos ==plist->tail_
{
if(plist->tail ==plist->tail->next)
plist->tail= NULL;
else
plist->tail = plist->before;
}
plist->before->next= plist->cur->next;
plist->cur= plist->before;
free(rpos);
(plist->numOfData)--;
return rdata;
}
int LCount(List *plist)
{
return plist->numOfData;
}
//CLinkedListMain.c
#include <stdio.h>
#include "CLinkedList.h"
int main()
{
//원형 연결 리스트의 생성 및 초기화
List list;
int data , i, nodeNum;
ListInit(&list);
//리스트에 5개의 데이터를 저장
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsertFront(&list, 2);
LInsertFront(&list, 1);
//리스트에 저장된 데이터를 연속 3회 출력
if(LFirst(&list, &data))
{
printf("%d ", data);
for(i=0;i<LCount(&list)*3-1; i++)
{
if(LNext(&list, &data))
printf("%d ", data);
}
}
printf("\n");
//2의 배수를 찾아서 모두 삭제
nodeNum = LCount(&list);
if(nodeNum !=0)
{
LFirst(&list, &data);
if(data %2 ==0)
LRemove(&list);
for(i=0;i<nodeNum-1;i++)
{
LNext (&list, &data);
if(data%2==0)
LRemove(&list);
}
}
//전체 데이터 1회 출력
if(LFirst(&list, &data))
{
printf("%d ", data);
for(i=0;i<LCount(&list)-1;i++)
{
if(LNext(&list, &data))
printf("%d ", data);
}
}
return 0;
}
===========================실행 결과===========================
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 3 5
이것으로 원형 연결 리스트에 대한 설명을 마친다.