Circular Linked List

Circular Linked List

 모든 노드가 원의 형태를 이루며 연결되어 있기 때문에,

사실상 머리와 꼬리의 구분이 없다.

다만 저장 순서를 근거로한 머리나 꼬리의 개념을 둘 뿐이다.

머리와 꼬리를 가리키는 포인터 변수를 두지않고

하나의 포인터 변수를 가지고 머리 또는 꼬리에 노드를 추가할 수 있게 한다.

꼬리를 가리키는 변수 : tail

머리를 가리키는 변수 : tail->next

변경하거나 추가할 함수

LNext

원형 연결리스트를 계속해서 순환하는 형태로 변경!

(이전 함수 그대로 써도 되지만 원형 연결리스트 특성을 반영)

앞과 뒤에 삽입이 가능한 두개의 함수 정의

LinsertFront, LInsert

void LInsert(List * plist, Data data); // 노드를 꼬리에 추가

void LInsertFront(List * plist, Data data); // 노드를 머리에 추가 

원형 연결리스트의 초기화 함수

void ListInit(List * plsit) // 모든 멤버를 NULL과 0으로 초기화

{

plist->tail = NULL;

plist ->cur = NULL;

plist->befor = NULL;

plist->numOfData = 0;

}

원형 연결리스트의 구현 : 첫번째 Node 추가

첫 번째 노드는 그 자체로 머리이자 꼬리이기 때문에 노드를 뒤에 추가하든 앞에 추가하든 결과가 동일

// LInsert와 LInsertFront의 공통 부분

void LInser~(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

if(plist->tail == NULL) 

{

plist->tail = newNode;           // ①

 newNode->next = newNode;  // ②

}

else

{

// 두번째 이후의 노드는 차이가 있음

}

원형 연결리스트의 구현 : 두번째 이후 Node 머리에 추가

void LInsertFront(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;    // (1)

plist->tail->next = newNode;             // (2)

}

(plist->numOfData)++;

}

원형 연결 리스트 구현 : 머리와 꼬리에 추가하는 과정 비교

tail이 가리키는 것이 꼬리Node, 

꼬리Node가 가리키는 것이 head

데이터의 순서는 동일, tail이 누구를 가리키냐만 차이

void LInsert(List * plist, Data data)

{

(... 생략)

   else 

{

newNode->next = plist->tail->next;

plist->tail->next = newNode;

      plist->tail = newNode;  //  LInsertFront 함수에는 없는 문장이며, 이것이 유일한 차이이다.

}

원형 연결 리스트 구현 : 조회 LFirst

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;

}

조회 LNext

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;

}

원형 연결 리스트 구현 : Node 삭제

핵심적인 부분은 앞서 dummy Node 기반 연결 리스트의 삭제와 다르지 않다.

하지만 다음의 두가지 예외 경우가 있다.

만약 삭제할 노드를 tail이 가리키는데, 그 노드가 마지막 노드라면 tail의 위치 조정이 필요하다.

tail이 가리키는 노드가 머리이자 꼬리인 경우엔 tail에 NULL을 저장한다.

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;

}

plist->before->next = plist->cur->next;

plist->cur = plist->before;

free(rpos);

(plist->numOfData)--;

return rdata;

}

원형 연결리스트 구현 예제

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;
        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;
    }
 
    plist->before->next = plist->cur->next;
    plist->cur = plist->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;
}

Output :

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

1 3 5