티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
이번에 소개하는 '원형 연결 리스트'는 앞서 소개한 단순 연결 리스트를 조금만 변경하면 쉽게 만들 수 있습니다. 따라서 그 구조를 이해하거나 구현하는 것은 어렵지 않습니다.
앞서 우리가 구현한 연결 리스트의 마지막 노드는 NULL을 가리켰습니다. 바로 이 마지막 노드가 첫 번째 노드를 가리키게 하면 이것이 바로 '원형 연결 리스트'가 됩니다.
그럼 꼬리가 다시 머리를 가리키게 하는 방법에 대해서 생각해 봅니다.
생각해보면 원형 연결 리스트를 구현하기 위해 tail 포인터가 필요하다는 생각이 듭니다. 하지만 그렇게 하면 원형 연결 리스트의 장점이 반감되어 버립니다. 원형 연결 리스트의 장점 중 하나는 다음과 같기 때문입니다.
"단순 연결 리스트처럼 머리와 꼬리를 가리키는 포인터 변수를 각각 두지 않아도, 하나의 포인터 변수만 있어도 머리 또는 꼬리에 노드를 간단히 추가할 수 있다."
그래서 변형된 모델이지만, 실제로는 보다 더 일반적인 모델로 인식되는 '변형된 원형 연결 리스트'를 사용합니다.
앞서 chapter 04에서 배운 연결 리스트는 head 포인터만 있고 이 head 포인터가 더미 노드를 가리키고 있었습니다. 그리고 새로 추가되는 노드들은 더미 노드 뒤로 삽입되었습니다. 그래서 이런 구조의 연결 리스트에서 꼬리를 찾고자 한다면 노드를 타고 타고 노드의 끝이 나올 때까지 찾아가야 합니다.
하지만 다르게 생각해보면 꼬리 찾기가 매우 수월해집니다. 바로 head 포인터가 가리키고 있는 더미 노드를 꼬리로 보는 것입니다. 그리고 head 포인터의 이름을 tail 포인터로 수정합니다. 새로운 노드가 추가될 때마다 tail 포인터가 가리키는 꼬리 노드 뒤로 삽입됩니다. 그리고 가장 먼저 삽입된 노드는 tail노드를 가리키도록 합니다. 이렇게 하면 꼬리 노드는 tail로 찾을 수 있고, 머리 노드는 tail->next로 찾을 수 있습니다.
(어떻게 이런 게 가능한지 다음의 코드로 보이겠습니다.
void LInsert(List* plist, LData data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
if(plist->tail == NULL) plist->tail = newNode;
else newNode->next = plist->tail->next;
plist->tail->next = newNode;
}위 코드는 아직 책에서 소개되진 않았고, 제가 직접 새로운 노드를 추가하는 함수를 구현해 본 것입니다. 위 코드대로라면 tail 포인터로 꼬리를 가리키고, 새로운 노드를 계속해서 머리에 붙이며, 노드들이 원형 연결을 이루도록 할 수 있습니다. 여기까지는 제 생각이며, 계속해서 저자의 설명을 보겠습니다.)
이어서 LFirst, LNext, LRemove 함수를 이용해서 간단한 헤더 파일을 구성하고자 합니다. 또 데이터를 저장하는 함수는 두 개를 정의합니다. 하나는 리스트의 머리에, 다른 하나는 리스트의 꼬리에 노드를 추가하기 위함입니다.
//CLinkedList.h 헤더 파일로 저장
#ifndef C_LINKEDLIST_H
#define C_LINKEDLIST_H
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct Node
{
Data data;
struct Node* next;
} Node;
typedef struct
{
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 Remove(List* plist);
int LCount(List* plist);
#endif원형 연결 리스트의 초기화는 단순 연결 리스트의 초기화만큼 간단합니다.
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));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
newNode->data = data;
if (plist->tail == NULL)
{
plist->tail = newNode;
newNode->next = plist->tail;
}
else
{
newNode->next = plist->tail->next;
plist->tail->next = newNode;
}
plist->numOfData++;
}새로 추가하는 노드가 첫 번째 노드일 경우 바로 tail 포인터가 가리키게 하고, tail->next가 자기 자신을 가리키도록 합니다. 이후 추가되는 노드부터는 꼬리의 뒤에 추가되도록 코드를 구성했습니다. 원형 연결 리스트에서 꼬리의 뒤는 머리가 위치하게 되므로 해당 함수는 머리에 노드를 추가하는 함수가 됩니다.
꼬리에 노드를 추가하는 함수는 머리에 노드를 추가하는 함수와 매우 유사합니다. 다만, 딱 한 가지만 차이가 납니다.
void LInsert(List* plist, Data data) //꼬리에 노드 추가
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
newNode->data = data;
if (plist->tail == NULL)
{
plist->tail = newNode;
newNode->next = plist->tail;
}
else
{
newNode->next = plist->tail->next;
plist->tail->next = newNode;
plist->tail = newNode; //유일한 차이점
}
plist->numOfData++;
}꼬리에 노드를 추가하는 함수를 보면 흥미롭습니다. 노드를 추가하는 과정이 머리에 노드를 추가하는 것과 똑같기 때문입니다. 유일하게 다른 것은 머리에 노드를 추가해놓고, 이 노드를 꼬리로 하겠다는 코드 한 줄이 삽입되었다는 것입니다. 그렇게 되면 결국 꼬리에 노드를 추가한 것과 같게 됩니다.
이제 데이터의 조회를 담당하는 LFirst 함수와 LNext 함수를 구현하겠습니다. 참조 위치를 표현하는 멤버는 cur와 before이 있습니다. 먼저 LFirst함수부터 구현하겠습니다.
LFirst함수는 조회를 위해 가장 먼저 사용되는 함수입니다. 해당 함수를 호출하면 참조 위치를 초기화하게 됩니다. 원형 연결 리스트에서는 cur가 머리를 가리키게 하고, before가 꼬리를 가리키게 합니다. 구현하면 다음과 같이 됩니다.
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;
}데이터를 입력받으면 가장 먼저 tail에 노드를 저장하게 되므로, tail에 저장된 노드가 있는지 확인합니다. 이후에는 before 포인터가 꼬리, cur 포인터가 머리를 가리키도록 초기화합니다.
LNext 함수는 이보다 더 간단합니다. cur 포인터와 before 포인터를 각각 다음 위치로 옮겨주기만 하면 됩니다.
int LNext(List* plist, Data* pdata)
{
plist->before = plist->cur;
plist->cur = plist->cur->next;
pdata = plist->cur->data;
return TRUE;
}위 함수를 보면 참조를 끝마치는 조건이 없습니다. 원형 연결 리스트는 꼬리에서 머리로 연결되어 있기 때문에 참조의 끝이 없어 계속해서 호출할 수 있습니다. 이것이 원형 연결 리스트에서 LNext 함수의 특징입니다.
(책에서는 다음과 같이 LNext 함수를 정의했습니다.
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;
}tail에 저장된 노드가 있는지를 확인하고 있습니다. 그런데 저는 이 코드가 불필요하다고 생각해서 제외했습니다. 왜냐하면 LNext함수는 LFirst 함수가 먼저 호출되어야 호출할 수 있습니다. 그리고 LFirst함수에서 이미 tail에 저장된 노드가 있는지를 확인하는 코드가 있습니다. 따라서 LNext함수에서 이런 코드는 불필요합니다.)
이제 노드를 삭제하는 함수 LRemove를 구현해 보겠습니다. 구현 방법은 단순 연결 리스트와 다르지 않습니다.
Data Remove(List* plist)
{
Node* delNode = plist->cur;
Data delData = delNode->data;
plist->before->next = plist->cur->next;
plist->cur = plist->before;
free(delNode);
plist->numOfData--;
return delData;
}위 함수는 단순 연결 리스트의 LRemove를 구현한 것입니다. 구현의 핵심은 다음과 같습니다.
- before->next가 cur->next를 가리키게 하는 것
- cur 포인터를 before 자리로 한 칸 이동시킬 것
원형 연결 리스트의 LRemove 함수는 여기에서 두 가지 예외상황을 더 고려해야 합니다.
- 삭제할 노드를 tail이 가리키는 경우
- 삭제할 노드가 하나밖에 없는 경우
삭제할 노드를 tail이 가리키고 있으면 삭제 후에는 tail 포인터가 저장하고 있는 주소에는 아무것도 남아 있지 않게 됩니다. 그래서 삭제 전에 cur 포인터와 마찬가지로 before 포인터가 가리키는 노드를 가리키도록 바꿔줘야 합니다.
그리고 남아 있는 노드가 하나밖에 없는데 해당 노드를 삭제하는 경우에도 마찬가지로 tail 포인터가 가리키는 대상이 사라지게 되므로, 이때는 tail 포인터에 NULL값을 저장해 주어야 합니다. 이를 구현하면 다음과 같습니다.
Data Remove(List* plist)
{
Node* delNode = plist->cur;
Data delData = delNode->data;
if (plist->tail == plist->cur)
{
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(delNode);
plist->numOfData--;
return delData;
}이제 원형 연결 리스트의 헤더 파일의 정의와 구현이 끝났습니다. 이를 하나의 프로젝트로 묶어 실행해 볼 차례입니다. 원형 연결 리스트를 테스트하기 위한 main 함수는 다음과 같습니다.
int main(void)
{
//원형 연결 리스트의 생성 및 초기화
List list;
int data;
ListInit(&list);
//리스트에 5개의 데이터를 저장
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsertFront(&list, 22);
LInsertFront(&list, 11);
//리스트에 저장된 데이터를 연속 3회 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
int i;
for (i = 0; i < LCount(&list) * 3 - 1; i++)
{
if (LNext(&list, &data)) printf("%d ", data);
}
}
printf("\n");
//2의 배수를 찾아서 모두 삭제
int nodeNum;
nodeNum = LCount(&list);
if (nodeNum != 0)
{
LFirst(&list, &data);
if (data % 2 == 0) LRemove(&list);
int i;
for (i = 0; i < nodeNum - 1; i++)
{
LNext(&list, &data);
if (data % 2 == 0) LRemove(&list);
}
}
//전체 데이터 1회 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
int i;
for (i = 0; i < LCount(&list) - 1; i++)
{
if (LNext(&list, &data)) printf("%d ", data);
}
}
return 0;
}전체 파일과 실행결과는 다음과 같습니다.
//CLinkedList.h 헤더 파일로 저장
#ifndef C_LINKEDLIST_H
#define C_LINKEDLIST_H
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct Node
{
Data data;
struct Node* next;
} Node;
typedef struct
{
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 "CLinkedList.h"
#include <stdio.h>
#include <stdlib.h>
void ListInit(List* plist)
{
plist->tail = NULL;
plist->cur = NULL;
plist->before = NULL;
plist->numOfData = 0;
}
void LInsert(List* plist, Data data) //꼬리에 노드 추가
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
newNode->data = data;
if (plist->tail == NULL)
{
plist->tail = newNode;
newNode->next = plist->tail;
}
else
{
newNode->next = plist->tail->next;
plist->tail->next = newNode;
plist->tail = newNode; //유일한 차이점
}
plist->numOfData++;
}
void LInsertFront(List* plist, Data data) //머리에 노드 추가
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
newNode->data = data;
if (plist->tail == NULL)
{
plist->tail = newNode;
newNode->next = plist->tail;
}
else
{
newNode->next = plist->tail->next;
plist->tail->next = 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)
{
plist->before = plist->cur;
plist->cur = plist->cur->next;
*pdata = plist->cur->data;
return TRUE;
}
Data LRemove(List* plist)
{
Node* delNode = plist->cur;
Data delData = delNode->data;
if (plist->tail == plist->cur)
{
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(delNode);
plist->numOfData--;
return delData;
}
int LCount(List* plist)
{
return plist->numOfData;
}//main.c 소스 파일로 저장
#include <stdio.h>
#include "CLinkedList.h"
int main(void)
{
//원형 연결 리스트의 생성 및 초기화
List list;
int data;
ListInit(&list);
//리스트에 5개의 데이터를 저장
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsertFront(&list, 22);
LInsertFront(&list, 11);
//리스트에 저장된 데이터를 연속 3회 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
int i;
for (i = 0; i < LCount(&list) * 3 - 1; i++)
{
if (LNext(&list, &data)) printf("%d ", data);
}
}
printf("\n");
//2의 배수를 찾아서 모두 삭제
int nodeNum;
nodeNum = LCount(&list);
if (nodeNum != 0)
{
LFirst(&list, &data);
if (data % 2 == 0) LRemove(&list);
int i;
for (i = 0; i < nodeNum - 1; i++)
{
LNext(&list, &data);
if (data % 2 == 0) LRemove(&list);
}
}
//전체 데이터 1회 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
int i;
for (i = 0; i < LCount(&list) - 1; i++)
{
if (LNext(&list, &data)) printf("%d ", data);
}
}
return 0;
}
/*
실행결과
11 22 3 4 5 11 22 3 4 5 11 22 3 4 5
11 3 5
*/'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 05. 양방향 연결 리스트 (0) | 2021.03.11 |
|---|---|
| 연습문제 05. 1 원형 연결 리스트의 활용 (0) | 2021.03.11 |
| 연습문제 04. 4 정렬의 기준으로 활용되는 함수의 정의 (0) | 2021.03.10 |
| Chapter 04. 연결 리스트의 정렬 삽입의 구현 (0) | 2021.03.10 |
| 연습문제 04. 3 연결 리스트에 구조체 변수의 주소 값 저장하기 (0) | 2021.03.10 |