[c/c++] 원형 연결 리스트 ( Circular Linked List )

< 이전 내용 >

• 단순 연결 리스트

 

안녕하세요 ! 우디입니다.🌞

오늘은 원형 연결 리스트 ( Circular Linked List )에 대해 알아봅시다 !

---

원형 연결 리스트 ( Circular Linked List )란 ?

처음과 끝이 없고, 리스트가 원형으로 순환하는 것을 말한다.

➤ 단순 연결 리스트와의 차이점은 마지막 노드의 링크가 NULL( 단순 연결 리스트 )이 아닌 맨 앞의 주소를 담고 있다는 것 !

 

원형 연결 리스트 ( Circular Linked List ) 구현

단순 연결 리스트의 구조체랑 동일합니다.

typedef int element; // 나중에 형변환 할때 유용하다
typedef struct ListNode{
    element data;          //데이터 필드
    struct ListNode *link; //링크 필드
}ListNode;

❌ 저는 헤드노드를 리스트의 맨 마지막 노드로 고정시켰습니다.

 

삽입

(1). 맨 앞쪽에 삽입하는 경우

xxxxxxxxxx
void insert_first(ListNode **phead, ListNode *node);

• phead : 헤드 포인터 (head) 에 대한 포인터 ( 여기에 head의 주소가 담긴다. )
• new_node : 새로운 노드를 가르키는 포인터

< Total >

xxxxxxxxxx
void first_insert_node(ListNode **phead, ListNode *node)
{
    if ((*phead) == NULL)//노드 초기화 역할 ( 초기화 함수 따로 안짜줬음 .)
    {
        node->link = node;
        *phead = node;
    }
    else
    {
        node->link = (*phead)->link;
        (*phead)->link = node;
    }
}

 

(2). 맨 뒷쪽에 삽입하는 경우

: (1)번의 과정 후 삽입하는 노드를 head 노드로 변경시켜주면 된다.

xxxxxxxxxx
void insert_last(ListNode **phead, ListNode *node);

• phead : 헤드 포인터 (head) 에 대한 포인터 ( 여기에 head의 주소가 담긴다. )
• node : 새로운 노드를 가르키는 포인터

< Total >

xxxxxxxxxx
void last_insert_node(ListNode **phead, ListNode *node)
{
    if ((*phead) == NULL)//노드 초기화 역할 ( 초기화 함수 따로 안짜줬음 .)
    {
        node->link = node;
        *phead = node;
    }
    else
    {
        node->link = (*phead)->link;//(*phead)해보기
        (*phead)->link = node;
        *phead = node;
    }
}

 

삭제

xxxxxxxxxx
void c_delete_node(ListNode **phead, ListNode *p, ListNode *removed);

• phead : 헤드 포인터 (head) 에 대한 포인터 ( 여기에 head의 주소가 담긴다. )
• p : 삭제될 위치의 선행노드를 가르키는 포인터 ( p 노드 다음에 삭제된다 . )
• removed : 삭제될 노드를 가르키는 포인터 ( ❗❗ 노드를 동적할당 받았으면 반드시 삭제할 노드는 연결리스트 변경 후 메모리 해제시켜주기❗❗ )

 

1. *phead ( head 값 ) 가 NULL 인 경우

: 바로 return 해준다.

 

2. removed (삭제할려고 하는 노드) 가 head 인 경우

: head 값을 head->link 노드로 변경해준다.

 

3. 가장 일반적인 경우

 

< Total >

xxxxxxxxxx
void c_delete_node(ListNode **phead, ListNode *p, ListNode *removed)
{  //1. 헤드가 널 2. head 포함 삭제 3. else
    if ((*phead) == NULL)
        return;
    else if((*phead)==removed)//head 를 head->link에 들어있는 노드로 변경
    {
        *phead = (*phead)->link;
        p->link = removed->link;
    }
    else
    {
        p->link = removed->link;
    }
    free(removed);
}

 

역순

xxxxxxxxxx
ListNode *c_reverse(ListNode *head)
{
    ListNode *p, *q, *r;//r이 q를 q가 p를 따라감
    p = head;
    q = NULL;
    do
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
        
    } while (p != head);
    p->link = q;//while 빠져나오면 p(head에 위치)의 link가 NULL이기 때문에 q 넣어줌.
    return (q);
}

 

탐색

xxxxxxxxxx
ListNode *c_search(ListNode *head, int x)
{
    ListNode *p = head;
    do {
        if (p->data == x) return p;
        p = p->link;
    } while (p != head);
    return 1;
}

 

출력

xxxxxxxxxx
void c_display_node(ListNode *head)
{
    ListNode *p;
    p = head;
    if (p == NULL)return;
    do
    {
        printf("%d ->", p->data);
        p = p->link;
    } while (p != head);
    printf("\n");
}

 

---

노드 동적 생성 , 삽입, 삭제 , 역순 , 탐색 , 출력

​x
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
​
typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode * link;
}ListNode;
​
ListNode *c_create_node(element data, ListNode *link)
{
    ListNode *new_node;
    new_node = (ListNode*)malloc(sizeof(ListNode));
    if (new_node == NULL)printf("메모리 할당 \n");
    new_node->data = data;
    new_node->link = link;
    return new_node;
}
​
void c_init_node(ListNode **phead)
{
    *phead = NULL;
}
​
void first_insert_node(ListNode **phead, ListNode *node)
{
    if ((*phead) == NULL)
    {
        node->link = node;
        *phead = node;
    }
    else
    {
        node->link = (*phead)->link;//(*phead)해보기하면 헤드의 주소가 들어감
        (*phead)->link = node;
    }
}
​
void last_insert_node(ListNode **phead, ListNode *node)
{
    if ((*phead) == NULL)
    {
        node->link = node;
        *phead = node;
    }
    else
    {
        node->link = (*phead)->link;//(*phead)해보기
        (*phead)->link = node;
        *phead = node;
    }
}
​
void c_delete_node(ListNode **phead, ListNode *p, ListNode *removed)//1. 헤드가 널 2. head 포함 삭제 3. else
{
    if ((*phead) == NULL)
        return;
    else if((*phead)==removed)//head 를 head->link에 들어있는 노드로 변경
    {
        *phead = (*phead)->link;
        p->link = removed->link;
    }
    else
    {
        p->link = removed->link;
    }
    free(removed);
}
​
void c_display_node(ListNode *head)
{
    ListNode *p;
    p = head;
    if (p == NULL)return;
    do
    {
        printf("%d ->", p->data);
        p = p->link;
    } while (p != head);
    printf("\n");
}
​
ListNode *c_search(ListNode *head, int x)
{
    ListNode *p = head;
    do {
        if (p->data == x) return p;
        p = p->link;
    } while (p != head);
    return 1;
}
​
ListNode *c_reverse(ListNode *head)
{
    ListNode *p, *q, *r;
    p = head;
    q = NULL;
    do
    {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
        
    } while (p != head);
    p->link = q;
    return (q);
}
​
int main()
{
    ListNode *list1 = NULL;
​
    first_insert_node(&list1, c_create_node(30, NULL));
    first_insert_node(&list1, c_create_node(20, NULL));
    last_insert_node(&list1, c_create_node(40, NULL));//head가 data 40이 들어있는 노드로 변경
​
    c_display_node(list1);//40->20->30
​
    ListNode *p;
    p = c_search(list1, 60);
    if (p == 1) printf("NO \n");
    else {
        printf("%d 탐색 성공 \n", p->data);
    }
    c_delete_node(&list1, c_search(list1, 30), c_search(list1, 40));
​
    c_display_node(list1);//20->30
​
    list1 = c_reverse(list1);
    c_display_node(list1);
​
​
    
}