이전 게시물까지 단일 연결리스트 (Singular Linked List)를 공부했습니다.
연결리스트는 크게 단일, 원형, 이중 리스트가 있고, 이를 조합해서 다양한 종류로 확장됩니다.
이번에는 원형 연결리스트 (Circular Linked List)를 알아보겠습니다.
원형 연결리스트
단일 연결리스와 원형 연결리스트는 일반적인 큐와 원형 큐 (환형 큐)의 관계와 동일합니다.
단방향으로만 연결됐던 연결리스트의 마지막 노드 (tail node)가 제일 처음 노드 (head node)와 연결됩니다.
가장 큰 특징은 하나의 노드에서 모든 노드로 접근이 가능해진다는 것입니다.
단일 연결리스트는 항상 head 또는 tail 중 한 방향으로만 접근할 수 있기 때문에 반대 방향의 노드는 참조할 수 없습니다.
하지만 원형 연결리스트는 모든 노드가 연결 되어있기 때문에 돌아돌아 가더라도 원하는 노드를 모두 참조할 수 있습니다.
1) 원형 연결리스트 ADT
ADT
Init_List(void) : 연결리스트를 초기화 합니다.
Add_First(ListMark *ls, int data) : 연결리스트의 가장 처음 노드에 노드를 추가합니다.
Add_Pos(ListMark *ls, int pos, int data) : 사용자가 원하는 위치에 노드를 추가합니다.
Delete_First(ListMark *ls) : 연결리스트의 가장 처음 노드를 삭제합니다.
Delete_Pos(ListMark *ls, int pos) : 사용자가 원하는 위치의 노드를 삭제합니다.
Reset_List(ListMark *ls) : 연결리스트의 모든 노드의 메모리를 반환하고, 연결리스트를 초기화 합니다.
Replace_Data(ListMark *ls, int pos, int data) : 원하는 위치에 있는 노드의 데이터를 변경합니다.
Search(ListMark *ls, int pos) : 특정 위치에 있는 노드의 데이터를 출력합니다.
Get_Length(ListMark *ls) : 연결리스트에 저장된 노드의 갯수를 반환합니다.
Print_List(ListMark *ls) : 연결리스트의 모든 노드에 저장된 데이터를 출력합니다.
원형 연결리스트를 구성하는 함수는 위와 같습니다.
본인이 구현하는 프로그램의 목적과 특성에 맞게 추가, 변경, 삭제 할 수 있습니다.
2) 원형 연결리스트 구현
원형 연결리스트를 구현하는 방법은 굉장히 단순합니다.
아래와 같이 단일 연결리스트의 마지막 노드 (ls->tail)의 next가 가장 처음 노드 (ls->head)를 가리키면 됩니다.
ls->tail->next = ls->head;
2-1) 원형 연결리스트 구조체 선언
원형 연결리스트를 구현하기 위해 필요한 구조체는 다음과 같습니다.
typedef struct NODE{
struct NODE *next;
int data;
} Node;
typedef struct LISTMARK{
Node *head;
Node *tail;
int size;
} ListMark;
음.. 저는 항상 크기가 큰 자료형을 먼저 선언하고 (위에서 struct NODE와 Node) 이후에 더 작은 크기의 자료형 (int)을 선언해줍니다.
이유는 아래 게시물의 하단을 참조해주세요.
2020/02/27 - [공부/c언어 자료구조] - [자료구조 C 언어] C 프로그래밍 자료구조 - 2 : 배열과 구조체
위의 구조체에서 head와 tail은 원형 연결리스트의 처음 노드와 끝 노드를 가리키는 구조체 포인터 입니다.
2-2) 연결리스트 초기화
ListMark *Init_List(void){
ListMark *ls = (ListMark *)malloc(sizeof(ListMark));
ls->head = NULL;
ls->tail = NULL;
ls->size = 0;
return ls;
}
head와 tail 노드가 모두 NULL을 참조하도록 초기화 합니다.
게시물 하단에 제시해드리겠지만 해당 함수는 다음과 같이 main 함수에서 사용합니다.
ListMark *ls = Init_List();
2-3) 원형 연결리스트의 노드 추가
원형 연결리스트에 노드와 함께 데이터를 추가합니다.
연결리스트의 노드는 항상 데이터와 다음 노드를 가리키는 링커가 포함됩니다.
주석과 함께 코드의 의미를 자세히 알아보겠습니다.
void Add_First(ListMark *ls, int data){
Node *tmp = (Node *)malloc(sizeof(Node)); // 여기에 데이터가 들어가야하니까 메모리를 동적할당 해줍니다
tmp->data = data; // tmp의 data (tmp->data)에 원하는 data (int data)를 저장합니다.
if(ls->head == NULL){ // 처음에 NULL로 초기화 했기 때문에, 추가된 데이터가 없을 때 head는 여전히 NULL 입니다.
ls->head = tmp; // 첫 노드는 head와 tail이 함께 가리킵니다.
ls->tail = tmp;
tmp->next = tmp; // 즉, head와 tail의 next는 다시 head와 tail을 가리킵니다. (자기 손가락으로 자기를 찌릅니다.)
}
else{ // 이전에 저장된 데이터가 존재 할 때
tmp->next = ls->head; // head 자리에 tmp가 들어가야하므로 tmp의 next가 head를 가리킵니다.
ls->tail->next = tmp; // 원형이기 때문에 마지막 노드는 가장 처음 노드를 가리킵니다.
ls->head = tmp; // 이전 head는 tmp의 next가 가리키고 있고, head의 주소를 tmp로 갱신합니다.
// 즉, 새로운 [head(== tmp)] -> [이전 head]가 됩니다.
}
ls->size++; // 노드가 추가되었기 때문에 size를 하나 증가시켜줍니다.
}
void Add_Pos(ListMark *ls, int pos, int data){
Node *tmp = (Node *)malloc(sizeof(Node)); // 여기에 데이터가 들어가야하니까 메모리를 동적할당 해줍니다.
Node *cur = ls->head; // 얘는 그냥 head를 가리키는 포인터기 때문에 메모리를 할당하지 않습니다.
tmp->data = data;
if(pos <= ls->size){ // 원하는 위치가 연결리스트의 내부에 존재하는지 확인한다.
if(pos == 1){ // 첫번째 위치에 넣는것과 Add_First는 동일합니다.
Add_First(ls, data);
}
else{
int n = pos-1; // 이거 head를 지표로만 쓰면 없어질 듯
// head를 더미 포인터로 쓰면 없어도 될 것 같습니다. (아래 반복문을 위해 추가했습니다.)
while(--(n)){ // pos == m 일 때, m-2 번 실행된다.
cur = cur->next;
}
// 나온 cur은 내가 넣고 싶은 위치 바로 앞
// cur 뒤에 내가 넣고 싶은 데이터를 넣는다
// 반복문 종료 후 cur은 pos의 바로 이전 노드와 동일합니다.
tmp->next = cur->next; // cur 다음에 tmp가 위치하기 때문에 cur의 next를 tmp가 가리킵니다.
cur->next = tmp; // 본래 cur->next는 tmp가 가리키고, 그 위치에 cur이 대신 들어갑니다.
ls->size++;
}
}
else{
puts("You entered wrong position.");
}
}
2-4) 원형 연결리스트의 노드 삭제
void Delete_First(ListMark *ls){ // 연결리스트의 첫번째 노드를 삭제합니다.
Node *cur; // 이번 함수에서는 데이터를 저장하는 역할이 아니기 때문에 메모리를 할당 할 필요가 없습니다.
Node *tmp;
cur = ls->head;
if(cur == NULL){ // cur이 head와 동일하기 때문에 cur이 NULL이면 연결리스트는 비어있는 상태입니다.
puts("List is empty");
}
else{
tmp = ls->head->next; // tmp는 head의 다음 노드입니다. 이후 새로운 head가 됩니다.
ls->tail->next = tmp; // tmp가 새로운 head가 되므로 tail은 tmp를 가리킵니다.
free(cur); // cur은 삭제 해야 할 첫번째 노드이므로 동적할당된 메모리를 반환합니다.
ls->head = tmp; // 새로운 head로 tmp를 임명합니다.
ls->size --;
}
}
void Delete_Pos(ListMark *ls, int pos){ // 원하는 위치의 노드를 삭제합니다.
Node *tmp;
Node *cur;
cur = ls->head;
if(pos<=ls->size){
if(pos == 1){
Delete_First(ls);
}
else{
int n = pos-1; // 이거 head를 지표로만 쓰면 없어질 듯
while(--n){ // pos == n 일 때, n-2 번 실행된다.
cur = cur->next;
}
// cur은 지워야 할 노드의 이전 노드입니다.
tmp = cur->next; // tmp는 지우고자 하는 노드입니다.
cur->next = tmp->next; // 자기(tmp)는 지워질 것이기 때문에 자기 옆자리를 앞 노드에게 맡깁니다.
free(tmp); // tmp에 할당된 메모리를 해제합니다.
ls->size--;
}
}
else{
puts("You entered wrong position.");
}
}
2-5) 원형 연결리스트 리셋, 데이터 교체
void Reset_List(ListMark *ls){ // 원형 연결리스트에 저장된 모든 노드의 메모리를 반환하고, 초기화 합니다.
Node *tmp;
Node *cur;
cur = ls->head;
while(cur != ls->tail){ // head에서 tail까지 cur이 변화하며, 메모리를 해제합니다.
tmp = cur->next; // cur은 해제되기 때문에 cur 다음 노드를 tmp에 임시로 저장합니다.
free(cur);
cur = tmp; // cur은 해제된 노드의 다음 노드가 됩니다.
ls->size--;
}
free(cur); // cur은 tail이기 때문에 마지막으로 tail까지 해제해줍니다.
ls->size--; // 다음 게시물 주제인 이중 연결리스트에서는 마지막에 tail이 남지 않게 while문의 조건문을 변경해줍니다. (비교해보세요.)
ls->head = NULL; // Init_List와 동일합니다.
ls->tail = NULL;
ls->size = 0;
}
void Replace_Data(ListMark *ls, int pos, int data){ // 원하는 위치에 있는 노드의 데이터를 변경합니다.
Node *cur;
cur = ls->head;
while(--pos){ // pos == n 일 때 n-1 번 실행됨
cur = cur->next;
}
// 반복문 이후 cur은 변경하고자 하는 노드가 됩니다.
cur->data = data;
}
2-6) 원형 연결리스트 데이터 검색, 길이 반환
void Search(ListMark *ls, int pos){ // 원하는 위치의 노드 데이터를 출력합니다.
Node *cur = ls->head;
puts("");
if(pos == 1){
printf("Data[%d] = %d.\n", pos, cur->data);
}
else{
int n = pos;
while(--n){
cur = cur->next;
}
// 반복문 이후 cur은 출력하고자 하는 위치의 노드가 됩니다.
printf("Data[%d] = %d.\n", pos, cur->data);
}
}
int Get_Length(ListMark *ls){ // 현재까지 원형 연결리스트에 저장된 노드의 갯수를 반환합니다.
Node *cur = ls->head;
int length = 0;
if(cur == NULL){
length = 0;
}
else{
while(cur != ls->tail){ // cur이 head부터 tail 바로 전까지 변화하며 length를 증가시킵니다.
cur = cur->next;
length++;
}
length++; // tail의 갯수를 포함합니다.
}
return length; // 사실 ls->size와 동일한 값을 가집니다.
}
2-7) 원형 연결리스트 데이터 출력
void Print_List(ListMark *ls){ // 연결리스트의 모든 데이터를 출력합니다.
Node *cur = ls->head;
puts("");
if(ls == NULL){ // Get_Length와 동일한데 갯수를 증가시키지 않고, 출력한다는 것만 다릅니다.
printf("List is empty.\n");
}
else{
int n = 1;
while(cur != ls->tail){
printf("Data[%d] = %d.\n", n, cur->data);
cur = cur->next;
n++;
}
printf("Data[%d] = %d.\n", n, cur->data);
}
puts("");
}
3) 원형 연결리스트 전체 코드 및 출력 결과
3-1) 전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef struct NODE{
struct NODE *next;
int data;
} Node;
typedef struct LISTMARK{
Node *head;
Node *tail;
int size;
} ListMark;
ListMark *Init_List(void){
ListMark *ls = (ListMark *)malloc(sizeof(ListMark));
ls->head = NULL;
ls->tail = NULL;
ls->size = 0;
return ls;
}
void Add_First(ListMark *ls, int data){
Node *tmp = (Node *)malloc(sizeof(Node));
tmp->data = data;
if(ls->head == NULL){
ls->head = tmp;
ls->tail = tmp;
tmp->next = tmp;
}
else{
tmp->next = ls->head;
ls->tail->next = tmp;
ls->head = tmp;
}
ls->size++;
}
void Add_Pos(ListMark *ls, int pos, int data){
Node *tmp = (Node *)malloc(sizeof(Node));
Node *cur = ls->head;
tmp->data = data;
if(pos <= ls->size){
if(pos == 1){
Add_First(ls, data);
}
else{
int n = pos-1; // 이거 head를 지표로만 쓰면 없어질 듯
while(--(n)){ // pos == n 일 때, n-2 번 실행된다.
cur = cur->next;
}
// 나온 cur은 내가 넣고 싶은 위치 바로 앞
// cur 뒤에 내가 넣고 싶은 데이터를 넣는다
tmp->next = cur->next;
cur->next = tmp;
ls->size++;
}
}
else{
puts("You entered wrong position.");
}
}
void Delete_First(ListMark *ls){
Node *cur;
Node *tmp;
cur = ls->head;
if(cur == NULL){
puts("List is empty");
}
else{
tmp = ls->head->next;
ls->tail->next = tmp;
free(cur);
ls->head = tmp;
ls->size --;
}
}
void Delete_Pos(ListMark *ls, int pos){
Node *tmp;
Node *cur;
cur = ls->head;
if(pos<=ls->size){
if(pos == 1){
Delete_First(ls);
}
else{
int n = pos-1; // 이거 head를 지표로만 쓰면 없어질 듯
while(--n){ // pos == n 일 때, n-2 번 실행된다.
cur = cur->next;
}
tmp = cur->next;
cur->next = tmp->next;
free(tmp);
ls->size--;
}
}
else{
puts("You entered wrong position.");
}
}
void Reset_List(ListMark *ls){
Node *tmp;
Node *cur;
cur = ls->head;
while(cur != ls->tail){
tmp = cur->next;
free(cur);
cur = tmp;
ls->size--;
}
free(cur);
ls->size--;
ls->head = NULL;
ls->tail = NULL;
ls->size = 0;
}
void Replace_Data(ListMark *ls, int pos, int data){
Node *cur;
cur = ls->head;
while(--pos){ // pos == n 일 때 n-1 번 실행됨
cur = cur->next;
}
cur->data = data;
}
void Search(ListMark *ls, int pos){
Node *cur = ls->head;
puts("");
if(pos == 1){
printf("Data[%d] = %d.\n", pos, cur->data);
}
else{
int n = pos;
while(--n){
cur = cur->next;
}
printf("Data[%d] = %d.\n", pos, cur->data);
}
}
int Get_Length(ListMark *ls){
Node *cur = ls->head;
int length = 0;
if(cur == NULL){
length = 0;
}
else{
while(cur != ls->tail){
cur = cur->next;
length++;
}
length++;
}
return length;
}
void Print_List(ListMark *ls){
Node *cur = ls->head;
puts("");
if(ls == NULL){
printf("List is empty.\n");
}
else{
int n = 1;
while(cur != ls->tail){
printf("Data[%d] = %d.\n", n, cur->data);
cur = cur->next;
n++;
}
printf("Data[%d] = %d.\n", n, cur->data);
}
puts("");
}
int main(void) {
ListMark *ls = Init_List();
Add_First(ls, 11);
Add_First(ls, 12);
Add_First(ls, 13);
Print_List(ls);
Add_Pos(ls, 2, 21);
Add_Pos(ls, 3, 22);
Print_List(ls);
Add_Pos(ls, 2, 21);
Print_List(ls);
Delete_First(ls);
Delete_First(ls);
Delete_First(ls);
Print_List(ls);
printf("ls->tail->next->data = %d.\n", ls->tail->next->data);
printf("Current Length = %d\n", Get_Length(ls));
Search(ls, 3);
Replace_Data(ls, 3 , 33);
Print_List(ls);
return 0;
}
3-2) 출력 결과
가장 중요한 부분은 tail의 next가 가리키는 노드의 data가 원형 연결리스트의 첫번째 노드인 head가 가지는 data와 동일하다는 것입니다.
다음 게시물에선 이중 연결리스트에 관해 설명 드리겠습니다.
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] C 프로그래밍 자료구조 - 11 : 트리, 이진 트리의 개념 (Tree, Binary Tree) (0) | 2020.03.11 |
|---|---|
| [자료구조 C 언어] C 프로그래밍 자료구조 - 10 : 이중 연결리스트 (Doubly Linked List) (0) | 2020.03.10 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 8 : 연결리스트를 사용한 큐 (Queue) (0) | 2020.03.05 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 7 : 연결리스트를 사용한 스택 (Stack) (0) | 2020.03.05 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 6 - 1 : 연결리스트 (Linked List) (추가, 삽입, 삭제, 검색, 뒤집기 등) (0) | 2020.03.05 |