지금까지 연결 리스트는 배열 기반 리스트와 DMY 노드를 head로 설정해서 구현하는 연결 리스트를 구현했다.
이번에는 '원형 연결 리스트' 에 대해 설명하고자 한다.
Ch 05. Circular Linked List (CLL)
지금부터 원형연결리스트는 그냥 CLL이라고 축약해서 부르겠다.
지금까지 만든 연결 리스트들은 마지막에 위치한 노드 (tail 포인터가 있는 리스트든 없는 리스트든 그 위치에 있는 노드라 생각하자.) 는 NULL을 가리켰다. tail->next = NULL 이였단 얘기.
근데 이번에 만드려는 원형 연결 리스트는, 이 마지막 노드가 NULL을 가리키는게 아니고 다시 첫번째 head가 가리키는 노드를 가리킨다.
일반적인 CLL은 위와 같은 구조에서, 데이터가 박새로이 추가되면 head부분에 데이터가 추가 되고, 기존에 있던 데이터들은 하나씩 뒤로 밀려나가는 구조다.
하지만, 가장 일반적으로 쓰이는 CLL은 이게 아니라고 한다. 그래서 더 일반적인 모델인 "변형된 CLL"을 여기서 설명해준다.
지금 위의 그림을 보면, 포인터는 head 포인터밖에 없다.
근데 만약, 여기서 머리가 아닌 꼬리에 새로운 노드를 추가하고 싶다면? 아마도 d1에서 d4까지 일일히 옮겨가서 새 노드를 추가해줘야 할거다. 번거롭지 않은가.
그런데, 만약 앞에서 잠시 잊혀졌던 tail포인터를 여기 적용시켜준다면?
이렇게, tail 포인터를 사용해서 꼬리에 노드를 추가하는 것도 앞보다 훨씬 쉬워진다.
만약 head 부분에 넣고 싶다면? head 포인터에 넣으면 될까?
물론, 그렇게 생각하는게 맞겠지만. 코딩을 하면서 구현을 할 땐 최대한 변수들을 적게 쓰고 간결하게 프로그램을 구현하면 코드가 보기도 좋고, 깔끔하다.
그래서, 굳이 여기선 head포인터를 쓰지 않기 위해 없애려고 한다.
? 그러면 어떻게 머리에 노드를 넣어요
tail포인터를 사용해 주면 된다.
만약, tail->next 에 노드를 추가해준다면?
!
CLL은 마지막 노드가 첫 노드와 연결되어 있어서, 머리부분에 노드를 추가하는 것과 똑같이 된다!!
그래서, CLL의 헤더파일을 짜 줄 때에 노드를 의미하는 구조체에는 head 포인터를 안 넣어도 된다.
/* CLL.h */
#ifndef __C_L_L_H__
#define __C_L_L_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); // 꼬리부분에 node 추가
void LInsertFront(List *plist, Data data); // 머리부분에 node 추가
int LFirst(List *plist, Data *pdata);
int LNext(List *plist, Data *pdata);
Data LRemove(List *plist);
int LCount(List *plist);
#endif뭐 앵간해선 그동안 만져온 연결리스트들이랑 다 비슷하다.
그런데 ADT 정의를 보면, LInsert가 하나가 아니다.
LInsert, LInsertFront. 총 두개가 있다. 왜 두개냐?
앞서 예시를 보여줬을때, 꼬리 부분에 노드를 추가할 수 있다고 했고, 머리 부분에도 노드를 추가할 수 있다고 했다. 그래서 case에 따라 따로 넣어줘야 하니까, ADT에서도 따로 나눠준거임.
ADT는 ListInit은 그냥 이제 너무 쉬우니까. 넘어가겠다.
LInsert 두 친구들을 보자.
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 {
// 대기!
}
(plist->numOfData)++;
}그냥 새로운 노드를 넣어주는 과정이다. if문 같은 경우는 기존에 존재하는 노드가 하나도 없으면 넣어주는 과정이고. else문은 왜 대기일까?
LInsert와 LInsertFront는 각각 else부분에서 차이가 난다. 나머지 부분은 같다.
그러면 LInsert부터 보자. (꼬리에 노드 추가)
.
.
} else {
newNode->next = plist->tail->next;
plist->tail->next = newNode;
plist->tail = newNode;
}
.
.
책 안보고 머리로 상상하면서 직접 구현한거라, 굳이 구체적인 설명은 적지 않겠다.
그 다음, LInsertFront. (머리에 노드 추가)
.
.
.
} else {
newNode->next = plist->tail->next;
plist->tail->next = newNode;;
}
.
.
.이렇다.
그 다음, 조회를 위해 필요한 LFirst와 LNext.
일단 CLL에서는 데이터 조회를 어떻게 하냐! 를 먼저 그림으로 보도록 하자.
이런 식으로, 가장 먼저 저장된 node부터 검문해줘야하니까. 위의 그림과 같이 데이터 조회가 진행된다. 그리고 추가로 알아둬야 할게, 그러면 저러다가 LNext에서 조회는 언제 끝내지? 라고 생각할 수도 있다. CLL은 리스트의 끝을 검사하지 않는다. 그냥 무한반복을 돌린다는 얘기다.
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;
}그 다음은 LRemove인데, 여기선 고려해줘야할 사항이 많다.
일단 기본적으로 LRemove가 어떻게 이뤄지는지 보도록 하자.
그냥, 이렇게만 보면 앞서 DMY기반 연결리스트와 다른게 없어 보인다.
그런데, 만약 이런 경우엔?
-
plist->tail 에 있는 node를 지우려고 한다 : plist->tail을 다시 지정해줘야 한다.
-
해당 노드를 삭제하려고 하는데, 리스트에 남은 노드가 하나밖에 없다 : 다시 "0의 상태"로 돌려줘야 한다. + 그리고 이 경우는 1번 중에서도 특이 케이스라고 생각하면 된다. 어짜피 지워야 할 애가 tail이거든.
이 경우들을 숙지하고 LRemove를 짜줘야 한다.
Data LRemove(List *plist) {
Node *rpos = plist->cur;
Data rdata = rpos->data;
if (rpos == plist->tail) { // 위의 1번 케이스.
if (plist->tail == plist->tail->next) {
plist->tail = NULL;
} // 1번 케이스 && 2번 케이스.
else plist->tail = plist->before;
}
plist->before->next = plist->cur->next;
plist->cur = plist->before;
free(rpos);
(plist->numOfData)--;
return rdata;
}이렇게 된다.
CLL은, 이정도로 Basic은 끝이다.
