원형연결리스트 삽입 구현하기(맨앞,중간,맨뒤)

원형연결리스트의 삽입의 3가지 경우(맨 앞, 중간, 맨 뒤)에 대해 간단하게 구현해봤습니다.

원형연결리스트에서는 head 노드를 항상 맨 뒤 노드를 가리키게 해야 삽입/삭제 구현 시 계산이 편리합니다.

head를 단순연결리스트 처럼 맨 앞 노드를 가리키게 한다면 삽입 시에 맨 앞 노드의 앞에 삽입해야 하므로 

맨 뒤 노드까지 탐색하는 번거로움이 있습니다. 그 이유는 맨 뒤 노드 다음 노드가 맨 처음 노드가 되기 때문입니다. 

head가 항상 맨 뒤 노드를 가리키게 한다면 맨 뒤 노드를 이용해서 삽입 후 head가 newNode를 가리키면 insert_last, 

아니면 insert_first가 되기 때문에 매우 간편하게 구현 할 수 있습니다. 

삽입함수에서 중간삽입의 경우는 "중간에 삽입한다."는 의미가 무조건 앞(pre)노드가 있어야 가능하므로 

pre가 없을 경우는 고려하지않았습니다.  그렇기 때문에 이에대한 오류처리는 하지않았습니다.

실제로 pre노드의 검색이 실패 할 경우(없는 값 뒤에 insert_middle할 경우) 프로그램은 무한루프에 빠집니다. 

코드

#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);
    printf("%d\n", p->data); // 마지막 노드 출력
}
 
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;    // (1)
        head->link = node;        // (2)
    }
    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;    // (1)
        head->link = node;        // (2)
        head = node;        // (3)
    }
    return head;    // 변경된 헤드 포인터를 반환한다. 
}
ListNode* searchNode(ListNode* head, int data)
{
    ListNode* temp;
    temp = head;
    while (temp != NULL)
    {
        if (temp->data == data)return temp;
        else
            temp = temp->link;
    }
    return temp;
}
ListNode* insert_middle(ListNode* head, int pre_data, int data)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = data;
    if (head == NULL)
    {
        head = newNode;
        newNode->link = newNode;
    }
    else
    {
        ListNode* pre = searchNode(head, pre_data);
        
            newNode->link = pre->link;
            pre->link = newNode;
            head = newNode;
    }
    return head;
}
// 원형 연결 리스트 테스트 프로그램
int main(void)
{
    ListNode* head = NULL;
 
    // list = 10->20->30->35->40
    head = insert_last(head, 20);
    head = insert_last(head, 30);
    head = insert_middle(head, 30, 35);
    head = insert_last(head, 40);
    head = insert_first(head, 10);
    print_list(head);
    return 0;
}
 

결과