Linked list II(Circular linked list)

1. 원형 연결 리스트

원형 연결 리스트: 마지막 노드가 첫 번째 노드를 가리키는 리스트

원형 연결 리스트는 마지막 노드를 head가, 첫 번째 노드는 head->link가 가리키고 있다.

1. 원형 연결 리스트 정의
   원칙적으로 헤드 포인터만 있으면 된다.

   ListNode *head;

2. 원형 리스트의 처음에 삽입
   새로운 노드의 링크인 node->link가 첫 번째 노드를 가리키게 하고, 마지막 노드의 링크가 node를 가리키게 하면 된다.

ListNode* insert_first(ListNode *head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    if(head == NULL){
    	head = node;
        node->link = head;
    }
    else{
    	node->link = head->link;
        head->link = node;
    }
    return head;
}

3. 원형 리스트의 끝에 삽입
   처음과 끝이 정해져있지 않아, head의 위치만 새로운 노드로 바꿔주면 된다.

ListNode* insert_last(ListNode *head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    if(head == NULL){
    	head = node;
        node->link = head;
    }
    else{
    	node->link = head->link;
        head->link = node;
    }
    return head;
}

4. 테스트 프로그램
   원형 리스트는 마지막 노드가 NULL이 아니기 때문에 헤드 포인터와 비교해야 하고, while 대신 do-while문을 써야 한다.

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode{
	element data;
    struct ListNode *link;
} ListNode;

//리스트의 항목 출력
void print_list(ListNode* head)
{
	ListNode* p;
    
    if(head == NULL) return;
    p = head->link;
    do{
    	printf("%d->", p->data);
        p = p->link;
    }while (p != head->link);
}

listNode* insert_first(ListNode *head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    if(head == NULL){
    	head = node; // head포인터가 node를 가리키게 함
        node->link = head; // 첫 번째 노드가 된 node가 자기자신을 가리키게 함
    }
    else{
    	node->link = head->link;
        head->link = node;
    }
    return head;
}

ListNode* insert_last(ListNode *head, element data)
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->data = data;
    if(head == NULL){
    	head = node;
        node->link = head;
    }
    else{
    	node->link = head->link;
        head->link = node;
        head = node;
    }
    return head;
}

//테스트 프로그램
int main(void)
{
	ListNode *head == NULL;
    
    head = inset_last(head, 20);
    head = inset_last(head, 30);
    head = inset_last(head, 40);
    head = inset_first(head, 10);
    print_list(head);
    return 0;
}

---

2. 원형 연결 리스트의 이용: 멀티 플레이어 게임

원형 연결리스트는 다음과 같은 곳에서 사용된다.

1. 컴퓨터에서 하나의 CPU로 여러 개의 프로그램을 실행할 때
2. 멀티 플래이어 게임
3. 원형 큐 만들기

다음은 멀티 플레이어 게임의 코드이다

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char element[100];
typedef struct ListNode{
	element data;
    struct ListNode *link;
}ListNode;

ListNode* insert_last(ListNode *head, element data)
{
	ListNode *node = (ListNode)malloc(sizeof(ListNode));
    strcpy(node->data, data);
    if(head == NULL){
    	head = node;
        node->link = head;
    }
    else{
    	node->link = head->link;
        head->link = node;
        head = node;
    }
    return head;
}

int main(void)
{
	ListNode *head = NULL;
    
    head = insert_last(head, "KIM");
    head = insert_last(head, "PARK");
    head = insert_last(head, "CHOI");
    
    ListNode* p = head->link;
    for(int i = 0; i < 10; i++){
    	printf("현재 차례=%s \n", p->data);
        p = p->link;
    }
    return 0;
}