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

원형 연결 리스트

개념

단순 연결리스트는 마지막 노드는 NULL을 가리켰다. 이 마지막 노드를 다시 첫 번째 노드를 가리키게 하면 그게 바로 원형 연결 리스트이다.

여기서 새 노드를 머리에 추가해 보겠다. 그러면 리스트는 다음의 형태가 된다.

이번엔 반대로 꼬리에 추가해보면 다음과 같다.

두 경우를 비교해보면 머리에 추가하든 꼬리에 추가하든 둘 다 2가 저장된 노드를 가리킨다는 것을 알 수 있다. 이러한 특성 때문에 head를 없애고 tail만 둔 변형된 연결 리스트가 나왔다. 형태는 아래와 같다.(보통 원형 연결 리스트라고 하면 변형된 원형 연결 리스트를 뜻함)

여기서 꼬리를 가리키는 포인터 변수는 tail이고, 머리를 가리키는 포인터 변수는 tail->next이다. 이로 인해 머리와 꼬리에 새로운 노드를 추가 할 수 있게 되었다.

원형 연결 리스트의 구현

CLinkedList.h

#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__
 
#define TRUE    1
#define FALSE    0
 
typedef int Data;
 
typedef struct _node
{
    Data data;
    struct _node * next;
} Node;
 
typedef struct _CLL
{
    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 <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"
 
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));
    newNode->data = data;
 
    if(plist->tail == NULL)  //노드가 아무것도 없을 경우
    {
        plist->tail = newNode;    //tail이 첫 번째 노드를 가리킴
        newNode->next = newNode; //첫 번째 노드는 자기 자신을 가리킴
    }
    else
    {
        newNode->next = plist->tail->next; //노드를 머리에 추가
        plist->tail->next = newNode;    //맨 뒤 노드가 맨 앞 노드를 가리킴
    }
 
    (plist->numOfData)++;
}
 
void LInsert(List * plist, Data data) //노드를 꼬리에 추가
{
    Node * newNode = (Node*)malloc(sizeof(Node));    
    newNode->data = data;
 
    if(plist->tail == NULL) 
    {
        plist->tail = newNode;
        newNode->next = newNode;
    }
    else 
    {
        newNode->next = plist->tail->next;
        plist->tail->next = newNode;
        plist->tail = 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)
{
    if(plist->tail == NULL)    // 저장된 노드가 없다면
        return FALSE;
 
    plist->before = plist->cur;
    plist->cur = plist->cur->next;
 
    *pdata = plist->cur->data;
    return TRUE;
}
 
Data LRemove(List * plist)
{
    Node * rpos = plist->cur;
    Data rdata = rpos->data;
 
    if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면
    {
        if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면
            plist->tail = NULL;
        else
            plist->tail = plist->before;  //tail의 위치를 before로 옮겨줌
    }
 
    plist->before->next = plist->cur->next; //삭제하는 노드의 앞 노드와 삭제하는 노드의 다음 노드를 연결
    plist->cur = plist->before;    //cur의 위치를 before로 옮겨줌
 
    free(rpos);
    (plist->numOfData)--;
    return rdata;
}
 
int LCount(List * plist)
{
    return plist->numOfData;
}

CLinkedListMain.c

#include <stdio.h>
#include "CLinkedList.h"
 
int main(void)
{
    // 원형 연결 리스트의 생성 및 초기화 ///////
    List list;
    int data, i, nodeNum;
    ListInit(&list);
 
    // 리스트에 5개의 데이터를 저장 /////// 
    LInsert(&list, 3);
    LInsert(&list, 4);
    LInsert(&list, 5);
    LInsertFront(&list, 2);
    LInsertFront(&list, 1);
    
    // 리스트에 저장된 데이터를 연속 3회 출력 ///////
    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        for(i=0; i<LCount(&list)*3-1; i++)
        {
            if(LNext(&list, &data))
                printf("%d ", data);
        }
    }
    printf("\n");
 
    // 2의 배수를 찾아서 모두 삭제 ///////
    nodeNum = LCount(&list);
 
    if(nodeNum != 0)
    {
        LFirst(&list, &data);
        if(data%2 == 0)
            LRemove(&list);
        
        for(i=0; i < nodeNum-1; i++)
        {
            LNext(&list, &data);
            if(data%2 == 0)
                LRemove(&list);
        }
    }
 
    // 전체 데이터 1회 출력 ///////
    if(LFirst(&list, &data))
    {
        printf("%d ", data);
        
        for(i=0; i<LCount(&list)-1; i++)
        {
            if(LNext(&list, &data))
                printf("%d ", data);
        }
    }
    return 0;
}

---------------------------------------------------

이 글은 열혈 자료구조를 읽고 정리한 글입니다.